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.
Mikhail Rudoy's user avatar
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. ...
usul's user avatar
  • 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 ...
Sasho Nikolov's user avatar
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) ...
J.-E. Pin's user avatar
  • 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 ...
Michaël Cadilhac's user avatar
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 ...
Mateus de Oliveira Oliveira's user avatar
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 ...
Daniel Apon's user avatar
  • 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 ...
Martin Berger's user avatar
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 ...
DanielM's user avatar
  • 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})$...
Joshua Grochow's user avatar
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.
Mohammad Al-Turkistany's user avatar
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 ...
Peter Shor 's user avatar
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 ...
PeaBrane's user avatar
  • 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 ...
Mikhail Rudoy's user avatar
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.
Vinicius dos Santos's user avatar
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.
Mohammad Al-Turkistany's user avatar
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 ...
Bashir's user avatar
  • 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
trahtman's user avatar
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 ...
Kaveh's user avatar
  • 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 "...
Thomas Klimpel's user avatar
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. ...
Bruno's user avatar
  • 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 ...
Damiano Mazza's user avatar
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/...
Student's user avatar
  • 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 ...
xrq's user avatar
  • 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.
Kaarel Hänni's user avatar
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