17
votes
Accepted
Is optimally solving the n×n×n Rubik's Cube NP-hard?
One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.
- 2,758
14
votes
Does Memcomputing really solve an NP-complete problem?
I feel this has been answered sufficiently in the comments, so to just sum everything up:
The authors do not claim P=NP, which is a statement about deterministic and nondeterministic Turing machines.
...
- 7,595
14
votes
Major unsolved problems in theoretical computer science?
Summary Table for Answers
Open Problems
Matrix Multiplication: Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations?
Graph Isomorphism: Is Graph Isomorphism in P?
Factoring: Is ...
12
votes
Approximating the sign rank of a matrix
Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that
there exists an efficiently computable ...
- 18.1k
8
votes
Does there exist a hardest DCFL?
The paper
J.-M. Autebert, Une note sur le cylindre des langages déterministes,
Theoretical Computer Science 8 (1979), 395-399
gives a short proof of the following result (credited to Greibach) ...
- 4,771
8
votes
Does there exist a hardest DCFL?
There actually is a hardest DCFL, which is a deterministic version of Greibach's; it was introduced by Sudborough in 78 in On
deterministic
context-free
languages,
multihead
automata,
and
the
...
- 3,946
8
votes
Does there exist a hardest DCFL?
An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original paper.
We show that every context-free language can be expressed ...
8
votes
Accepted
Learning with (Signed) Errors
(wow! after three years of time passing, this is now easy to answer. funny how that goes! --Daniel)
This "Learning with (Signed) Errors" (LWSE) problem, as invented-and-stated above by me (three ...
- 5,961
8
votes
Accepted
List of (unsolved) complexity problems arising from PL
Pippenger's (1) from 1996 shows that (under some assumptions) strict (CBV) functional programming languages are asympotically slower than imperative languages. It is open whether Pippenger's result ...
- 11.4k
6
votes
Does Memcomputing really solve an NP-complete problem?
I would like to add some additional information to Daniel Primosch's answer from above. The figure with the results from the paper he cited is accurate. We got in touch with the authors a while back ...
- 73
5
votes
Major unsolved problems in theoretical computer science?
Getting an O(1) factor approximation algorithm in polytime for the Maximum Independent Set of Rectangles.
This is one of the biggest open problems in Computational Geometry. Recently, Anna Adamaszek ...
4
votes
Is the 3-sphere recognition problem NP-complete?
This paper shows (though I have not verified it) that 3-sphere recognition* is in coNP assuming GRH:
Raphael Zentner. Integer homology 3-spheres admit irreducible representations in $SL(2,\mathbb{C})$...
- 36.9k
4
votes
"Refined" list of open problems in TCS
There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.
- 20.8k
3
votes
Accepted
Noisy channel coding theorem in quantum information
You have two questions here.
Why can't Shannon's Noisy Coding Theorem be used for a quantum channel?
What gaps are there to proving a quantum noisy channel coding theorem?
I will concentrate on the ...
- 24.3k
3
votes
Does Memcomputing really solve an NP-complete problem?
The title of the memcomputing article is clearly problematic from a complexity theorist's viewpoint. There is no rigorous proof that the analog implementation of memcomputing would converge in ...
- 131
3
votes
Deciding whether an NC${}^0_3$ circuit computes a permutation or not
This problem with $k=3$ is coNP-hard (and therefore coNP-complete).
To prove this, I will reduce from 3-SAT to the complement of this problem (for a given $NC_3^0$ circuit, does the circuit enact a ...
- 2,758
3
votes
"Refined" list of open problems in TCS
There is a list of open problems in graph theory and combinatorics collected and maintained by Douglas B. West.
This page maintains a list of lists of open problems in parameterized complexity.
- 1,868
3
votes
Positive topological ordering, take 3
This paper, Obtaining a triangular matrix by independent row-column permutations Fertin, Rusu, and Vialette, shows that the problem is NP-complete for binary square matrices.
- 20.8k
3
votes
Projective Plane of Order 12
There is a conjecture saying that, if sigma(n)>2n, then there is neiether a finite projective plane (FPP) of order n, nor a complete set of mutually orthogonal Latin square (CMOLS) that corresponds to ...
- 41
3
votes
Status of Cerny Conjecture?
see ArXiv:
1405.2435 cs.FL "The length of a minimal synchronizing word and the \v{C}erny conjecture" with the story of study
https://arxiv.org/pdf/1405.2435.pdf
- 31
2
votes
Accepted
In regards to the tautologies of a polynomially-bounded propositional proof system
Your question is like asking what is the class of formulas for the problem SAT?
In the definition of SAT it is fixed to some fixed class,
say those based on $\{\lnot, \land, \lor\}$
but it doesn't ...
- 21.5k
2
votes
Massive online collaboration for solving open problem in theoretical computer science
If a massively online collaboration is set up, then it should try to focus on problems with a reasonable chance of success. The three classical construction problems of antiquity are known as "...
- 3,033
2
votes
Multiplying n polynomials of degree 1
In computer algebra, this computation is usually referred as computing the subproduct tree and is a subroutine of multipoint evaluation and interpolation. See for instance: von zur Gathen, Gerhard. ...
- 4,439
2
votes
"Refined" list of open problems in TCS
There's the TLCA List of Open Problems, collecting unsolved problems in $\lambda$-calculi and related areas, such as proof theory, semantics and theory of programming languages. It is maintained by ...
- 5,273
2
votes
Open/unsolved problems in (computational) random matrix theory / matrix completion?
Not sure if this is the kind of thing you want but here is something I find fascinating : This particular breakthrough paper's proof technique is in a sense "random matrix theory", https://arxiv.org/...
- 644
2
votes
Areas of research and open problems in functional programming
The computational implications of homotopy type theory & higher type theory.
Homotopy type theory was invented and developed by a group of computer scientists and mathematicians as a new ...
- 1,175
1
vote
A conjecture related to the Cerny conjecture - counterexample/reference request
I found a partial answer to question 2. The same idea is discussed in the last 10 minutes of this lecture.
- 91
1
vote
Major unsolved problems in theoretical computer science?
In general, what is the relationship between time and space complexity classes?
There are many unresolved questions such as:
Is $PTIME = NLOGSPACE$?
Is $PTIME = DLOGSPACE$?
Is $PTIME = PSPACE$?
Is $...
Only top scored, non community-wiki answers of a minimum length are eligible