General Mathematics

1807 Submissions

[4] viXra:1807.0197 [pdf] submitted on 2018-07-09 09:58:18

Packing Triangles is Harder Than Previously Thought

Authors: Thinh D. Nguyen
Comments: 3 Pages.

In this work, we will take one problem, namely Packing Triangles as an example of combinatorial optimization problems. We show that if one has ever loved reading Prasolov’s books, then one should not try to find efficient algorithm for various restricted cases of this problem.
Category: General Mathematics

[3] viXra:1807.0125 [pdf] submitted on 2018-07-05 14:59:41

Shellability is NP-complete

Authors: Thinh Nguyen
Comments: 19 Pages.

We prove that for every d≥2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d≥2 and k≥0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL- shellable.
Category: General Mathematics

[2] viXra:1807.0098 [pdf] submitted on 2018-07-03 06:11:19

Erd ̋os-Szekeres is NP-Hard in 3 Dimensions and What Now?

Authors: Thinh Nguyen
Comments: 4 Pages.

The Erd ̋os-Szekeres theorem states that, for every $k$, there is a number $n_k$ such that every set of $n_k$ points in general position in the plane contains a subset of $k$ points in convex position. If we ask the same question for subsets whose convex hull does not contain any other point from the set, this is not true: as shown by Horton, there are sets of arbitrary size that do not contain an empty 7-gon. These questions have also been studied extensively from a computational point of view, and polynomial time algorithms for finding the largest (empty) convex set have been given for the planar case. In higher dimension, it is not known how to compute such a set efficiently. In this paper, we show that already in 3 dimensions no polynomial time algorithm exists for determining the largest (empty) convex set (unless $P$=$NP$), by proving that the corresponding decision problem is $NP$-hard. This answers a question by Dobkin, Edelsbrunner and Overmars from 1990. As a corollary, we derive a similar result for the closely related problem of testing weak $ε$-nets in $R^3$ . Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is $co-NP$-hard. Finally, we make several suggestions for further research on the subject.
Category: General Mathematics

[1] viXra:1807.0031 [pdf] replaced on 2018-07-02 07:45:23

The Unreasonable Expectation of Mathematics

Authors: August Lau
Comments: 6 Pages.

Mathematics has been highly effective in its application of formalism to the real world. It spans from physical science to data science. Mathematical algorithm affects our everyday life. Mathematization (converting data to equations or mathematical forms) has been very successful. It has led to comments like “the unreasonable effectiveness of mathematics,” but we might have “unreasonable expectation of mathematics.”
Category: General Mathematics