All Questions
598 questions with no upvoted or accepted answers
27
votes
0
answers
1k
views
Computational complexity of topological K-theory
I am a novice with K-theory trying to understand what is and what is not possible.
Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the cohomology of $X$ with ...
- 666
22
votes
0
answers
1k
views
Do we know how to determine the $2^{2020}$ decimal of $\sqrt{2}$?
In the case of $\dfrac{1}{7^{800}}$ it's easy, to find the $2^{2020}$ decimal, but what about the simplest of the irrational numbers.
Question: Do we know how to determine the $2^{2020}$ decimal of $\...
- 4,074
21
votes
0
answers
441
views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
- 4,535
19
votes
0
answers
513
views
Checking Mertens and the like in less than linear time or less than $\sqrt{x}$ space
Say you want to check that $|\sum_{n\leq x} \mu(n)|\leq \sqrt{x}$ for all
$x\leq X$. (I am actually interested in checking that $\sum_{n\leq x} \mu(n)/n|\leq c/\sqrt{x}$, where $c$ is a constant, and ...
- 20.2k
19
votes
0
answers
782
views
Reference request: Parallel processor theorem of William Thurston
Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...
- 15.4k
17
votes
0
answers
449
views
Splay trees and Thompson's group $F$
( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...
- 992
15
votes
0
answers
487
views
Does the Angel have to be really smart?
My question is about the computational complexity of the Angel's strategy in the Angels and Devils game, tl;dr does the Angel have a polynomial time strategy.
I'm a big Conway fan, so as you can ...
- 6,652
15
votes
0
answers
424
views
Complexity classes for BSS machines
Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...
- 21.2k
15
votes
0
answers
1k
views
Razborov's response to Almost Natural Proofs
This post is about Natural Proofs barrier in computational complexity.
There are two recent papers related to this. They are:
Amplifying lower bounds by means of self-reducibility by Eric Allender ...
- 5,502
15
votes
1
answer
794
views
Are there any natural theories T for which P=NP implies T proves P=NP?
The qualifier "natural" is meant to exclude examples like "PA + P=NP" or "PA + True $\Pi_1$".
For concreteness, let's say that "natural" = sound, computably enumerable, with a feasible proof-checker.
...
- 333
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
13
votes
0
answers
229
views
Primitive recursive and feasible presentations for nonstandard models of arithmetic
Let us define a countable model $\cal{M}$ = $(M,+_M ,\cdot_M, <_M)$ of $Q$ (Robinson arithmetic) to have a (primitive) recursive presentation if $\cal{M}$ is isomorphic to $(\omega, \oplus, \...
- 17.7k
13
votes
0
answers
713
views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
- 3,897
13
votes
0
answers
2k
views
How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?
EDIT: This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.
Here are Vinay Deolalikar's paper, and Richard Lipton's first post ...
- 5,502
12
votes
0
answers
158
views
Known obstruction for efficient computation of Stable homotopy groups?
Computation of stable homotopy groups (for example of sphere) is hard, but still, not as hard as unstable ones.
For unstable homotopy groups there are some results showing that there cannot be ...
- 42.4k
12
votes
0
answers
447
views
Geometric complexity theory for finite fields
Geometric complexity theory (GCT) is an approach via algebraic geometry and representation theory towards the P vs. NP problems and related problems Ketan D. Mulmuley.
More precisely, the idea is to ...
- 2,576
12
votes
0
answers
902
views
Primes and Parity
This problem is motivated by the polymath4 project. There, the aim was to find an efficient deterministic algorithm for finding a prime larger than $N$. The hope was to find a polynomial algorithm in $...
- 24.7k
10
votes
0
answers
453
views
Fast method to verify if a point belongs to a given convex $d$-polytope
We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
- 1,677
10
votes
0
answers
722
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
- 109k
10
votes
0
answers
270
views
Collapsing the Linear Time Hierarchy and finite axiomatizability of bounded arithmetic
It is well known that if ${\bf T_2}$ (or $I\Delta_0+\Omega_1$) is finitely axiomatizable, then the Polynomial Hierarchy collapses.
Q. Is there any similar relation between $I\Delta_0$ and Linear ...
- 1,689
10
votes
0
answers
2k
views
Is Witten's new method of quantization useful for geometric complexity theory?
The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used ...
- 321
9
votes
0
answers
2k
views
Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere
Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
- 311
9
votes
0
answers
378
views
Surprising mathematical consequences of of $\mathbf{P} = \mathbf{NP}$
I got interested in the mathematical consequences of $P = NP $ after reading this post, Any important consequences with presupposition of P≠NP .
Wang conjectured that if a finite set of Wang tiles ...
- 2,993
9
votes
0
answers
246
views
Is there an efficient algorithm for testing isomorphism of projective planes?
Isomorphism testing is a core problem in computational complexity. Recently, Babai has shown that Graph Isomorphism problem for general graphs can be solved in quasipolynomial time. Long time before ...
- 2,993
9
votes
0
answers
221
views
Is there a ``Ladner's Theorem" for the PH-vs-PSPACE scenario?
Like a statement of the kind, ``If the Polynomial Hierarchy (PH) $\neq$ PSPACE then there exists $L \in PSPACE \backslash PH$ which is not PSPACE-complete"?
Or is there something else that states ...
- 1,893
9
votes
0
answers
2k
views
Weighted Hamming distance
Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, ...
- 24.8k
8
votes
0
answers
164
views
Is there a substructure-preservation result for FOL in finite model theory?
It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find ...
- 21.2k
8
votes
0
answers
360
views
Worst-case complexity of calculating homotopy groups of spheres
Is the best known worst-case running time for calculating the homotopy groups of spheres $\pi_n(S^k)$ bounded by a finite tower of exponentials? How high is a tower? Does $O(2^{2^{2^{2^{n+k}}}})$ ...
- 827
8
votes
0
answers
237
views
Size of 3-SAT assignments
Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is ...
- 3,979
8
votes
0
answers
462
views
Inverse polynomial map $\mathbb{Z}^2\to\mathbb{Z}^2$ growing faster than $2^{2^n}$
Let $P, Q\in \mathbb{Z}[x, y]$ be polynomials with zero constant terms. Assume the induced map $\phi_{P, Q}:\mathbb{Z}^2\to\mathbb{Z}^2$ is injective. An example is $P=x+x^3 y^2, Q=y+x^2 y^3$.
Can the ...
- 219
8
votes
0
answers
88
views
Is recognizing if a Latin square is isotopic to its transpose more efficient than computing its symmetry group?
Ihrig and Ihrig (2007) described a mathematical method for determining if a Latin square is isotopic to its transpose (where isotopic Latin squares vary by permuting the rows, columns and symbols). ...
- 1,327
8
votes
0
answers
231
views
Complexity of integer programming with added predicates
A classical theorem in Integer Programming by Lenstra says that any integer system
$$A x \le b$$
can be solved in polynomial time, where $A \in \mathbb{Z}^{m \times n}, x \in \mathbb{Z}^n, b \in \...
- 343
8
votes
0
answers
226
views
Is Hankelability NP-hard?
This question was previously asked on cstheory but with no answers or substantive comments.
I am trying to write code to detect if a matrix is a permutation of a Hankel matrix. Here is the spec.
...
- 3,377
8
votes
0
answers
200
views
Ricocheting pinball-like shot: Complexity?
Suppose one has $n$ perfect two-sided mirror segments in the plane $\mathbb{R}^2$.
The segments are open, excluding their endpoints.
They are disjoint as closed segments, i.e., no pair shares an ...
- 151k
8
votes
0
answers
225
views
Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?
Landau's function
$g(n)$ is the largest order of an element of the symmetric group $S_n$.
Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$.
In general $g(n)$ is ...
- 25.4k
8
votes
0
answers
288
views
Recognizing sequences sortable by transpositions?
While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from ...
- 2,993
8
votes
0
answers
143
views
Can the isomorphism relation for countable models become harder when adding finitely many constants?
I am particularly interesting in the case where $T$ is o-minimal, but I would be interested in any theory $T$ (or even an $L_{\omega_1,\omega}$-sentence) which has this property.
Context: view the ...
- 1,979
8
votes
0
answers
1k
views
Computational complexity of multiplication in a nilpotent group?
What is the computational complexity of multiplication in a Carnot group ?
Background: A Carnot group is a real nilpotent Lie group $N$ whose Lie algebra $Lie(N)$ admits a direct sum decomposition
...
- 785
8
votes
0
answers
1k
views
Infinite Linear Programming
I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...
- 133
8
votes
0
answers
753
views
Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?
Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?
I know it is NP-complete for the ...
- 161
7
votes
0
answers
203
views
Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs
Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...
- 965
7
votes
0
answers
524
views
Zero-knowledge proofs for answers to the $P=NP$ question
Are there zero-knowledge proofs for every answer to the $P=NP$ question?
For instance, if you have a polynomial-time algorithm of moderate complexity for the graph-coloring problem, then it is easy to ...
- 13.2k
7
votes
0
answers
179
views
The provability logic of $I\Delta_0+\Omega_1 $ and complexity theory
Almost 30 years ago, a number of folks in provability logic tried to show that GL (see for instance the excellent survey by Rineke Verbrugge here) is indeed the logic of $I\Delta_0+\Omega_1$ (in the ...
- 7,853
7
votes
0
answers
122
views
Does the problem of recognizing 3DORG-graphs have polynomial complexity?
A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...
- 4,535
7
votes
0
answers
93
views
Combinatorial region-halfplane incidence structures
I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate.
Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...
- 5,590
7
votes
0
answers
342
views
Multidimensional hook length formula
A well-known hook length formula states that the number of ways to arrange the elements of $[n]$ in a Young tableau with $n$ cells so that all columns and rows are increasing is $\frac{n!}{\prod_c h(c)...
- 5,590
7
votes
0
answers
1k
views
Closed-form solution of a linear programming question
Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \...
7
votes
0
answers
3k
views
Why is solving polynomial systems NP hard?
Solving polynomial systems is known to be a NP hard problem; however it is not completely clear to me where this complexity comes from.
My interest is in the case of systems of multivariate ...
7
votes
0
answers
267
views
Can primes be (almost) random sequence in von Mises sense?
Random models for primes (such as Cramer's model) have been extensively used for informal justification of various conjectures involving primes. It is crucial to understand in what sense sequence of ...
- 7,182
7
votes
0
answers
480
views
Is simultaneous diophantine approximation (in a weaker sense) NP hard?
The traditional problem of simultaneous diophantine approximation is: Given a set of rational numbers $g_1,\ldots,g_d$, an integer $N$, and a rational $\gamma>0$, is there an integer $W$ with $1\...
