All Questions
1,809 questions
11
votes
2
answers
964
views
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
- 1,826
11
votes
2
answers
746
views
Ordinals and complexity classes
What is the least recursive ordinal $\alpha$ such that there is no algorithm in complexity class $\mathsf{P}$ which implements a well-ordering of $\mathbb{N}$ with order type $\alpha$? (where the size ...
- 6,819
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
11
votes
5
answers
2k
views
Zero knowledge proof of equality
Alice and Bob each secretly chooses an integer between 1 and 10, a and b. They want to know (with high probability) whether or ...
- 2,967
11
votes
1
answer
712
views
Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?
According to this source (p. 10), determining whether a simplicial complex is a simplicial sphere (the sphere recognition problem) is undecidable.
According to this source, determining whether a ...
- 13.6k
11
votes
1
answer
950
views
Computational complexity of computing simplicial homology
Is there any literature regarding the fastest known algorithm to compute the homology groups of a simplicial complex (on n vertices)? What about computing the fundamental group? The context is to tell ...
- 123
11
votes
1
answer
860
views
Counting colored rook configurations in the cube - when is it even?
Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,...
- 1,088
11
votes
3
answers
496
views
Finite objects for which isomorphism is NP-hard or harder?
Are there finite objects for which deciding isomorphism
is NP-hard or harder?
Graphs and groups are not solutions.
Searching the web didn't return answer for me.
Partial result based on Chow's ...
- 25.4k
11
votes
2
answers
668
views
What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?
Disjoint sets $A$ and $B$ are computably inseparable, if there
is no computable separating set, a computable set $C$ containing $A$ and disjoint from $B$. The
existence of c.e. computably inseparable ...
- 236k
11
votes
1
answer
2k
views
Does EXP $\in$ P/poly imply NP=RP?
I guess the answer is that this unknown.
Maybe this implies some "lowness" result on NP relative to BPP?
11
votes
3
answers
4k
views
Is this a well known NP-complete problem?
I came across this problem recently and I wanted to know whether it was a well known NP-complete problem. I checked the library but could not find anything that matched exactly.
Given a directed ...
- 111
11
votes
1
answer
661
views
Descriptive complexity theoretic-characterizations of P and NP
Prompted by Vinay Deolalikar's purported proof of P != NP, I've been reading up on Descriptive Complexity for some background material.
The major successes of Descriptive Complexity include Fagin's ...
- 2,019
11
votes
2
answers
2k
views
How hard is it to solve SAT if the promise is that it has an odd number of solutions?
SAT is NP-complete even if we promise that it has an even number of solutions (by introducing a new dummy variable). However, USAT (when the promise is that it has exactly one solution) is not known ...
- 18.7k
11
votes
1
answer
410
views
Complexity of counting regions in hyperplane arrangements
Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...
- 17k
11
votes
3
answers
3k
views
Do you know a faster algorithm to color planar graphs?
while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet.
The program can be ...
- 351
11
votes
1
answer
457
views
Comparing two numbers given their factorization
I'm not an expert, but given the integer factorization of two numbers $a,b$:
$$a = p_{i_1}^{a_1}...p_{i_n}^{a_n}, \quad b = p_{j_1}^{b_1}...p_{j_m}^{b_m}$$
What is the time and space compexity of ...
- 1,602
11
votes
2
answers
964
views
What Turing-Complete models of computation carry a notion of time complexity that "agrees" with that of Turing Machines?
Certain models of computation are technically Turing-Complete, but cannot feasibly simulate a Turing Machine within the usual time constraints we hope for. One example of this is Godel's recursive ...
- 1,389
11
votes
2
answers
1k
views
An algorithm to find non-trivial linear dependencies
This question is inspired by another MO question about special stratifications of equivariant Grassmannians, that turned out to be a problem of computing non-trivial circuits in a vector matroid. To ...
- 56.6k
11
votes
1
answer
420
views
The complexity of the leading fractional bit of a power of a rational number
On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...
- 4,636
11
votes
1
answer
404
views
Traveling Salesman Problem on finite group
Given a finite group $H$, define a norm on $H$ to be a function $f : H \rightarrow \mathbb{R}_{\geq 0}$ satisfying:
$f(x) = 0 \iff x = e$ is the identity;
$\forall x \in H$, we have $f(x) = f(x^{-1})$...
- 12.4k
11
votes
1
answer
504
views
How hard is it to guess Kuperberg's certificate of knottedness?
Kuperberg's Knottedness is in $\mathsf{NP}$, modulo GRH provides a certificate that a knot $K$ given by a knot diagram on $c$ crossings is not trivial. The certificate is a prime $p$, along with a ...
- 2,185
11
votes
1
answer
552
views
complexity of counting homomorphisms
This is a question I have thought about and asked a number of people, but have never got an answer beyond "It should be true that..."
Given a finitely generated group $G$ (eg. a link group $G_L:=\...
- 1,639
10
votes
5
answers
645
views
Syntactically capturing complexity classes
Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that ...
user10891
10
votes
2
answers
3k
views
How do you tell if a system of linear inequalities has a solution?
A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
- 693
10
votes
3
answers
1k
views
Is there a formal notion of what we do when we 'Let X be ...'?
This is likely an elementary question to logicians or theoretical computer scientists, but I'm less than adequately informed on either topic and don't know where to find the answer. Please excuse the ...
- 1,376
10
votes
2
answers
418
views
Do there exist groups with word problems in arbitrary P-degrees?
This has been posted on TCS stack exchange for a while here and hasn't gotten any answers, so I'm trying again here.
It has been known for a long time that, given any r.e. Turing degree, there is a ...
- 258
10
votes
2
answers
647
views
Bounded Arithmetic vs Complexity Theory
In this post, when I talk about bounded arithmetic theories,
I mean the theories of arithmetic according to "Logical Foundations of Proof Complexity", which capture the complexity classes between $AC^...
- 103
10
votes
1
answer
734
views
Polynomial-time complexity and a question and a remark of Serre
My question is about the theory of complexity, but let me first explain my motivation, which comes from number theory or more precisely from trying to understand a question/conjecture of Serre and a ...
- 26k
10
votes
1
answer
519
views
Can $N!$ be computed in less than $\mathcal{O}(N)$ operations?
The standard algorithm to compute the factorial function $N!$ via repeated multiplications has complexity $\mathcal{O}(N)$, in the model in which each operation costs 1, no matter how many digits the ...
- 766
10
votes
1
answer
890
views
How hard is it to compute the Davenport constant?
The Davenport constant $D(G)$ of a finite abelian group $(G,+)$ is the least positive integer $k$ such that every sequence in $G$ of length $k$ has a zero-sum (nonempty) subsequence.
It seems that the ...
- 1,446
10
votes
2
answers
696
views
Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time
I have the book "Handbook of Computational Group Theory", by Derek Holt, and in it is a section on finding the transversal of a subgroup. Recall a transversal of a subgroup $H$ of $G$ is a single ...
- 333
10
votes
3
answers
6k
views
Solving a system of linear inequalities -- what is the dimension of the solution set?
It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the ...
- 7,857
10
votes
1
answer
396
views
Groups whose word problem can be solved in constant time
Given a finitely generated group $G$, define an encoding of $G$ to be a one-to-one function $\Phi:G\to \bigcup_n \{0,1\}^n$ that sends each group element to a unique finite word. For $a,b\in G$, ...
- 799
10
votes
3
answers
985
views
Approximate volume computation and lattice point enumeration - hardness
Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation.
...
- 13.9k
10
votes
1
answer
513
views
What is the complexity of finding a third Hamilton Cycle in cubic graph?
According to Smith Theorem: if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known ...
user39815
10
votes
1
answer
676
views
How hard is Heyting satisfiability, i.e. the constructive version of SAT? In particular, is 2-HSAT NL-complete or is it harder?
First of all, is it clear what I mean by $k$-HSAT?
I'm assuming that for $k>2$, $k$-HSAT is NP-complete, but the details of the reductions between $k$-HSAT and $k$-SAT aren't obvious to me.
I'm ...
- 457
10
votes
2
answers
3k
views
Can a number be factored quickly, given the sum of its prime factors?
This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...
- 9,114
10
votes
1
answer
595
views
Fast checking that overdetermined polynomial system does not have a solution
As a result of some inductive procedure for each $n$ I have a system of about $n^2$ polynomial equations with $n$ variables with integer coefficients, which can be precisely computed. As the system is ...
- 728
10
votes
1
answer
385
views
Do sparse DAGs can have large min-cuts?
For a graph $G$, let $e(G)$ denote the number of its edges, and $c_k(G)$ the smallest number
of edges that must be removed in order to destroy all paths of length $\geq k+1$.
Note that $c_1(G)\geq c_2(...
- 213
10
votes
1
answer
2k
views
Sum of difference moduli vs. sum of modulus differences
This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself.
Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
- 33.8k
10
votes
1
answer
411
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...
- 37.7k
10
votes
1
answer
1k
views
Can we invert barycentric subdivision?
With apologies to fellow algebraic topologists, I confess that I have no idea how to answer this innocent-looking question:
(1) Let's say we know that a finite simplicial complex $S$ is the ...
- 15.5k
10
votes
2
answers
478
views
Most efficient reductions between NP-complete problems
Assume I need to solve an NP-complete problem, for which problem-specific methods (e.g. efficient heuristics or exponential algorithms faster than naive one) are not well developed. If the size of ...
- 781
10
votes
1
answer
910
views
Finding Two Rainbow Spanning Trees
Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.
Is the following problem NP-...
- 1,288
10
votes
3
answers
649
views
Efficiently getting bits of N! ?
Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?
i.e....
- 513
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
3
answers
3k
views
Complete problems for randomized complexity classes
It is believed that $BPP$ has no complete problems. Even for $BPP^O$ for a suitable oracle $O$ it is believed not to have complete problems, unless P=BPP. I wonder if the class MA (the randomized ...
- 273