# Tag Info

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.

### 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. ...

### 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 ...

### 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 ...

### 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) ...

### 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 ...

### 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 ...
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 ...
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 ...

### 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 ...

### 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 ...

### 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})$...

### "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.
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 ...

### 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 ...

### 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 ...

### "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.

### 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.

### 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 ...

### 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
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 ...

### 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 "...

### 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. ...

### "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 ...

### 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/...

### 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 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.
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