Questions tagged [open-problem]
Problems known to be open in the literature and any problem that, after being posed, is decided to be open by the community.
79
questions
4
votes
0
answers
142
views
Is there a 'mathematical program' to separate P from BQP?
This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999).
Usually, such programs are marked by long and ...
- 225
234
votes
60
answers
97k
views
Major unsolved problems in theoretical computer science?
Wikipedia only lists two problems under "unsolved problems in computer science":
P = NP?
The existence of one-way functions
What are other major problems that should be added to this list?
Rules:
...
16
votes
3
answers
1k
views
Is the 3-sphere recognition problem NP-complete?
It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere
is in NP, via work by
Saul Schleimer in 2004: "Sphere recognition lies in NP"
arXiv:math/0407047v1 [math.GT].
...
0
votes
0
answers
70
views
The hardness of active learning with fixed budget
I have been looking for theoretical papers studying this question of the hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (particular ...
- 65
4
votes
0
answers
123
views
Exploding number of homomorphisms
I'm trying to tackle the following problem: given two graphs $A$ and $B$, if there exists a graph $D$ such that $\hom(A, D) > \hom(B, D)$ (i.e. there is more homomorphisms from $A$ to $D$ than from ...
10
votes
4
answers
4k
views
Does Memcomputing really solve an NP-complete problem?
I came across an article published in Science "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states", which makes some pretty astonishing claims.
...
- 131
19
votes
2
answers
6k
views
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ...
- 37.3k
2
votes
0
answers
123
views
Open problem on *Finite Memory Clocks* by Tom Cover
This problem was proposed by Tom Cover in Open Problems in Communication and Computation (Cover and Gopinath, eds), 1987:
How does one tell time when the number of states in the clock is
insufficient ...
4
votes
4
answers
499
views
Are there alternatives to using polynomials in defining the different notions of efficient computation?
Is invoking polynomials in defining the different notions of efficient computation the real obstacle to resolve the P vs NP problem? Do we need a paradigm shift by redefining what constitute an ...
- 359
62
votes
13
answers
9k
views
Open problems on the frontiers of TCS
In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment:
I think we should distinguish between major open problems that are viewed ...
- 359
12
votes
2
answers
2k
views
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf
If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$.
If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\...
23
votes
0
answers
2k
views
$\Delta = 57, d=2$ Moore Graph
I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.
You may recall that Hoffman and ...
38
votes
2
answers
3k
views
Multiplying n polynomials of degree 1
The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.
You can do $O(n \...
- 4,630
30
votes
0
answers
792
views
The complexity of checking whether two DAG have the same number of topological sorts
This problem is highly related to the CNF one.
Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".
...
- 2,309
69
votes
10
answers
9k
views
Are there any open problems left about DFAs?
After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
- 10.5k
3
votes
1
answer
424
views
Noisy channel coding theorem in quantum information
Why Shannon's noisy channel coding theorem can't be used for quantum communication applications?
Schumacher proved the first Noiseless theorem and there are quantum error correction mechanisms out ...
- 24.8k
15
votes
3
answers
681
views
"Refined" list of open problems in TCS
In the conference on learning theory (COLT), a list of open problems is published every year, for example, the list of 2019.
The open problems are being submitted and peer reviewed, which makes this ...
- 5,483
37
votes
1
answer
1k
views
Efficiently computable function as a counter-example to Sarnak's Mobius conjecture
Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis.
Conjecture. Let $\mu(k)$ ...
- 111
20
votes
4
answers
1k
views
Positive topological ordering, take 3
Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix?
This question is motivated by this problem:
Positive topological ordering
...
- 9,269
4
votes
1
answer
483
views
Areas of research and open problems in functional programming [closed]
What are the major areas of functional programming that require more research and development? For example, I know a lot of people are asking for dependent types in Haskell, and someone at my uni is ...
- 1,175
4
votes
0
answers
112
views
Open Problems About Nowhere-Dense Classes of Graphs
I'm writing a survey about nowhere-dense graphs. I would like to list some of the main open problems in the field. In particular I would like to list problems of the following form.
The problem has ...
- 636
8
votes
1
answer
223
views
A conjecture related to the Cerny conjecture - counterexample/reference request
The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a ...
- 91
2
votes
0
answers
73
views
Complexity of comparing extended integer power towers
Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
- 643
129
votes
11
answers
12k
views
How hard is unshuffling a string?
A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a ...
- 20.9k
20
votes
0
answers
637
views
Identifying Reducible/Irreducible polynomials over $Z[x]$
It is well known LLL algorithm provides a fully polynomial algorithm to factor a reducible primitive polynomial over $\mathbb{Z}[x]$.
Say one only seeks to identify whether a given polynomial over $\...
- 1,132
1
vote
0
answers
59
views
Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity
I am wondering if this is a topic that has had research done...
If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...
- 111
65
votes
10
answers
12k
views
One Stack, Two Queues
background
Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
- 2,577
12
votes
2
answers
1k
views
List of number theoretic or algebraic problems in various complexity classes
I am looking for a list about the known or unknown complexity of various number theoretic /algebraic problems. For example,
GCD in $NC^1$ is open,
factoring in $P$ is open,
computing sheaf ...
- 37.3k
17
votes
1
answer
512
views
List of (unsolved) complexity problems arising from PL
What are some major, open computational complexity problems that arise from programming languages, especially program analysis and compilation? I am looking for problems on the lines of "the time ...
- 11.4k
1
vote
1
answer
361
views
Open/unsolved problems in (computational) random matrix theory / matrix completion?
I was wondering what some open problems are in random matrix theory (especially those of interest to TCS people/so mainly non-asymptotic things, I imagine). Also, and relatedly, what are remaining/...
- 654
40
votes
3
answers
10k
views
Is optimally solving the n×n×n Rubik's Cube NP-hard?
Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
- 2,768
19
votes
2
answers
2k
views
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 ...
- 31
1
vote
0
answers
233
views
What progress is being made on $NP \cap coNP$ having complete problems? [closed]
I'm very curious about this and have a proof sketch that it does not in the answers below. The reasons I'm currently thinking about this is because of the new paper on the class $PTFNP$ which can be ...
- 12.9k
14
votes
2
answers
1k
views
Projective Plane of Order 12
Objective: Settle the conjecture that there is no projective plane of order 12.
In 1989, using computer search on a Cray, Lam proved that no projective plane of order 10 exists. Now that God's ...
CommunityBot
- 1
27
votes
2
answers
755
views
Deciding whether an NC${}^0_3$ circuit computes a permutation or not
I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered.
A Boolean circuit is called an NC0k circuit ...
CommunityBot
- 1
7
votes
0
answers
812
views
Does PEG contain CFG?
Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable ...
- 21.6k
12
votes
3
answers
477
views
Does there exist a hardest DCFL?
Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, ...
- 6,470
0
votes
1
answer
288
views
In regards to the tautologies of a polynomially-bounded propositional proof system
In the book 'Logical Foundations of Proof Complexity', co-authored by Stephen Cook, the following definition is given:
A proof-system $F$ is said to be polynomially-bounded if there is a polynomial p(...
- 21.6k
20
votes
2
answers
957
views
Problems between NC and P: How many have been resolved from this list?
In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo (PS) (PDF), there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (...
- 19k
25
votes
2
answers
1k
views
Approximating the sign rank of a matrix
The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in ...
- 18.2k
10
votes
1
answer
378
views
Learning with (Signed) Errors
$\underline{\bf Background}$
In 2005, Regev [1] introduced the Learning with Errors (LWE) problem, a generalization of the Learning Parity with Error problem. The assumption of this problem's ...
- 6,001
12
votes
4
answers
1k
views
Problems not known to be PSPACE-complete
What are problems with the following properties:
1) they are restriction of (possibly well known) problems that are PSPACE-complete;
2) the restricted versions are in PSPACE, but it is an open ...
CommunityBot
- 1
4
votes
0
answers
545
views
Why can't we have superlinear bounds on Boolean circuit size for an explicit function?
I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other ...
- 9,269
3
votes
1
answer
419
views
Log Rank Conjecture Collaborative Approach [closed]
Recently a post was made in Mathoverflow seeking possible avenues for collaborative projects.
I made a proposal for Log Rank conjecture in https://mathoverflow.net/questions/219638/proposals-for-...
CommunityBot
- 1
11
votes
2
answers
733
views
Massive online collaboration for solving open problem in theoretical computer science
In Polymath projects a large group work on an open problem.
What kind of problems seem to work best in this framework?
Are there any good candidates for a polymath project in theoretical computer ...
- 21.6k
25
votes
1
answer
1k
views
Is it still open to determine the complexity of computing the treewidth of planar graphs?
For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-...
CommunityBot
- 1
5
votes
2
answers
1k
views
Research problems in communication complexity
There have been many open challenges questions in this forum.
For instance,
Research and open challenges in Programming Language Theory
What are current open problems in compiler theory?
...
CommunityBot
- 1
7
votes
1
answer
499
views
Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?
I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).
I am particularly ...
- 101
16
votes
1
answer
605
views
Integer linear programming in logarithmic number of variables
I read that integer linear programming is solvable in polynominal time if the number $n$ of variables is fixed, i.e. $n \in O(1)$. If the number of variables grows logarithmically, i.e. $n \in O(\...
- 3,698
16
votes
0
answers
489
views
Is graph coloring complete for poly-APX?
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
- 6,470