Most Popular
1500 questions
19
votes
3 answers
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is either unsatisfiable or has a unique solution.…
Devil
- 419
- 2
- 9
19
votes
3 answers
"The" category of Turing machines?
Disclaimer: I know very little about complexity theory.
I'm sorry but there is really no way to ask this question without being (terribly) concise:
What should be the morphisms in "the" category of Turing machines?
This is obviously subjective…
Saal Hardali
- 301
- 1
- 6
19
votes
5 answers
Why is it important to prove that a problem is NP-complete?
Am I correct in understanding that proving a problem NP complete is a research success? If so why?
Ali
- 301
- 1
- 7
19
votes
4 answers
"All-different hypergraph coloring" - known problem?
I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently colored. More specifically, I am looking at the case…
Falk Hüffner
- 1,023
- 9
- 13
19
votes
1 answer
Minor closed properties that are explicitly MSO expressible
Below, MSO denotes the monadic second order logic of graphs with vertex-set and edge-set quantifications.
Let $\mathcal{F}$ be a minor closed family of graphs. It follows from Robertson and Seymour's graph minor theory that $\mathcal{F}$ is…
Mateus de Oliveira Oliveira
- 3,052
- 21
- 27
19
votes
3 answers
How common is phase transition in NP-complete problems?
It is well known that many NP-complete problems exhibit phase transition. I am interested here in phase transition with respect to containment in the language, rather than the hardness of the input, relative to an algorithm.
To make the concept…
Andras Farago
- 11,396
- 37
- 70
19
votes
1 answer
Division by two of functions in #P
Let $F$ be an integer valued function such that $2F$ is in $\#P$. Does it follow that $F$ is in $\#P$? Are there reasons to believe this is unlikely to always hold? Any references I should know about?
Somewhat surprisingly, this situation came up…
Igor Pak
- 812
- 5
- 15
19
votes
2 answers
Status of Cerny Conjecture?
A DFA has a synchronizing word if there is a string that sends any state of the DFA to a single state. In ‘The Cerny Conjecture for Aperiodic Automata” by A. N. Trahtman (Discrete Mathematics and Theoretical Computer Science vol. 9:2, 2007,…
Nobody
- 295
- 4
- 13
19
votes
2 answers
Is there a non-deterministic linear time algorithm for CNF-SAT?
The decision problem CNF-SAT can be described as follows:
Input: A boolean formula $\phi$ in conjunctive normal form.
Question: Does there exist a variable assignment that satisfies $\phi$?
I'm considering several different approaches for solving…
Michael Wehar
- 5,127
- 1
- 24
- 54
19
votes
1 answer
Time complexity with irrational exponent?
Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?
Andras Farago
- 11,396
- 37
- 70
19
votes
4 answers
Math talk: Theorem about git revision control system?
I would like to give a mathematics talk on the git revision control system. It is now widely used in mathematics as well as in the computer science industry. For example, the HoTT (Homotopy Type Theory) community uses it, and it is the go to system…
Rex Butler
- 337
- 2
- 7
19
votes
1 answer
Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$
In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his factorization algorithm. The standard algorithm outputs $r'$,…
Frédéric Grosshans
- 815
- 6
- 15
19
votes
3 answers
Computation of reals: floating point vs TTE vs domain theory vs etc
Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised exact computation of reals. Clearly, the problem…
SorcererofDM
- 523
- 2
- 7
19
votes
2 answers
"Embedding" a language in itself
Main/General Question
Let $L$ be a language. Define the languages $L_i$ with $L_0 = L$ and
$$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$$
for $i \geq 1$. Consider $\hat{L} = \bigcup L_i$. So, we repeatedly "embed" $L$ into itself to obtain…
John Machacek
- 407
- 2
- 9
19
votes
2 answers
Internal Regret in Online Convex Optimization
Zinkevich's "online convex optimization" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generalizes "regret minimization" learning algorithms from a linear settings to a convex setting and gives good "external regret". Is there a similar…
Noam
- 9,369
- 47
- 58