Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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,615
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,831
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
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
4 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

"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

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

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
3 votes

Can you find a counterexample / disprove my P=NP solution?

From what I can tell, you have proposed a (heuristic) algorithm for solving the Satisfiability Problem. But you have not given an argument for the correctness of your algorithm or an analysis of the ...
NaturalLogZ's user avatar
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
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.7k
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,514
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
  • 654
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