Most Popular
1500 questions
29
votes
3 answers
Is NPI contained in P/poly?
It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP}…
Vanessa
- 2,151
- 12
- 21
29
votes
3 answers
A Notion of Monotone Quantum Circuits
In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the monotone Boolean circuits model.
My question is…
Gil Kalai
- 6,033
- 35
- 73
29
votes
3 answers
What does one mean by heuristic statistical physics arguments?
I have heard that there are heuristic arguments in statistical physics that yield results in probability theory for which rigorous proofs are either unknown or very difficult to arrive at. What is a simple toy example of such a phenomenon?
It would…
arnab
- 7,000
- 1
- 38
- 55
28
votes
4 answers
Complexity of minimising polynomial formula size
Let $f(x_1,\dots,x_n)$ be a degree $d$ polynomial in $n$ variables over $\mathbb{F}_2$, where $d$ is constant (say 2 or 3). I would like to find the smallest formula for $f$, where "formula" and "formula size" are defined in the obvious way (eg. the…
Ashley Montanaro
- 2,013
- 18
- 21
28
votes
2 answers
Maximal/maximum independent sets
Is there something known about the class of graphs with the property that all maximal independent sets have the same cardinality and are therefore maximum ISs?
For example, take a set of points in the plane and consider the graph of intersections…
László Kozma
- 1,336
- 1
- 10
- 16
28
votes
2 answers
Why is there an enormous difference between SAT solvers?
SAT solvers are very important in algebraic attacks, for example walksat and minisat.
However, when solving the benchmark problems available here there is an enormous performance difference between the two - Walksat is much faster than minisat for…
ir01
- 383
- 2
- 7
28
votes
5 answers
Vertex Cover applications in the real world
What applications does the Vertex Cover Problem have in the real world?
Which industry or research projects use actually implemented software that is based on theoretical results for the Vertex Cover problem? In particular, are any of the following…
scatman
- 311
- 1
- 3
- 4
28
votes
17 answers
Examples where insight from geometry was useful for solving something completely non-geometric
One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think of a triplet of numbers as a point in 3-d and…
Vinayak Pathak
- 1,631
- 10
- 22
28
votes
1 answer
Shor's factoring algorithm help
I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm.
Given an $N$ we want to factor, we choose a random $x$ which has order $r$.
The first step involves setting up the registers and applying the Hadamard…
Callum
- 283
- 3
- 4
28
votes
3 answers
How to produce a random graph that does not have a Hamiltonian cycle?
Let class A denote all the graphs of size $n$ which have a Hamiltonian cycle. It is easy to produce a random graph from this class--take $n$ isolated nodes, add a random Hamiltonian cycle and then add edges randomly.
Let class B denote all the…
Jagadish
- 1,955
- 21
- 27
28
votes
2 answers
Finding a prime greater than a given bound
Is a deterministic polynomial-time algorithm known for the following problem:
Input: a natural number $n$ (in binary encoding)
Output: a prime number $p > n$.
(According to a list of open problems by Leonard Adleman, the problem was open in 1995.)…
Vincenzo
- 751
- 6
- 11
28
votes
2 answers
Formally Verified Complexity Theory
Is there any ongoing project to formally verify the theorems and proofs of complexity theory using a proof assistant like Coq? Are there any boundaries to doing this?
Samuel Schlesinger
- 1,572
- 8
- 20
28
votes
3 answers
Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?
Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$?
Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of factoring (does n have a factor of size at most k),…
Joshua Grochow
- 37,260
- 4
- 129
- 228
28
votes
4 answers
What evidence is there that Graph Isomorphism is not in $P$?
Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete nor in $P$), I am interested in known evidences…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
28
votes
5 answers
Is it a rule that discrete problems are NP-hard and continuous problems are not?
In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually through gradient techniques. Are there exceptions to…
alekdimi
- 391
- 3
- 6