Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
49 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 ...
0
votes
1answer
143 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/...
17
votes
1answer
297 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 ...
1
vote
0answers
71 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 ...
1
vote
0answers
211 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 ...
9
votes
1answer
1k 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. ...
5
votes
0answers
316 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 ...
0
votes
1answer
167 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(...
12
votes
3answers
288 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, ...
3
votes
0answers
217 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 ...
3
votes
1answer
326 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-...
10
votes
2answers
641 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 ...
22
votes
1answer
595 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-...
19
votes
0answers
605 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 ...
12
votes
2answers
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 ...
5
votes
2answers
707 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? ...
12
votes
4answers
778 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 ...
7
votes
1answer
398 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 ...
16
votes
1answer
462 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(\...
7
votes
0answers
142 views

Examples of open problems solved through application of a theorem already known

Are there good examples of reasonable open problems in TCS that had an 'obvious' solution via application of a theorem found in mathematics probably found a few decades earlier but went unnoticed in ...
2
votes
2answers
295 views

What is the asymptotic time complexity of the number of steps of “Half Or Triple Plus One” ( HOTPO)?

The "Half Or Triple Plus One" process goes as follows: start with $x=n$ for some value of $n$ if ($x$ is odd) $x = 3x+1$ else $x = \frac{x}{2}$ if ($x$ > 1) goto (2) ...
16
votes
0answers
410 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 ...
58
votes
10answers
6k 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'...
18
votes
0answers
542 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 $\...
30
votes
4answers
14k views

Research and open challenges in Programming Language Theory

In the spirit of some general discussions like this one, I'm opening this thread with the intention to gather opinions on what are the open challenges and hot topics in research on programming ...
10
votes
1answer
448 views

Why does the log-rank conjecture use rank over the reals?

In communication complexity, the log-rank conjecture states that $$cc(M) = (\log rk(M))^{O(1)}$$ Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a matrix)...
9
votes
1answer
257 views

On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$

We know that $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$. From Savitch's Theorem, $\mathcal{N\!L}\subseteq\mathcal{L}^2$, and, from Space Hierarchy Teorem, $\...
5
votes
1answer
826 views

Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem? [duplicate]

Possible Duplicate: Implications of unprovability of $P\neq NP$ I shortly came across Gödels incompleteness theorem again and I wondered, since so much time has been spent on trying to answer ...
27
votes
2answers
691 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 ...
10
votes
0answers
237 views

What are the most recent developments in small-depth quantum circuits?

Back in 2005, Scott Aaronson posted a list of 10 "semi-grand" challenges for quantum computing theory which contained the following challenge: The power of small-depth quantum circuits. Is $BQP = ...
9
votes
1answer
286 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 ...
14
votes
2answers
3k 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 ripe for such problems"). ...
12
votes
2answers
3k views

Optimal algorithm for finding the girth of a sparse graph?

I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity. I thought about some modification on Tarjan's algorithm for ...
0
votes
2answers
507 views

largest language class for which inclusion is decidable

am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable. am also ...
1
vote
1answer
321 views

Questions about computing matrix rigidity

Matrix rigidity was introduced by Valiant in 1977: The rigidity $Rig_M(r)$ of boolean matrix $M$ over GF(2) is the smallest number of entries of $M$ that must be changed in order to reduce its ...
-1
votes
2answers
745 views

What progress has been made to prove whether or not p=np? [closed]

I know that it is still one of the biggest mysteries of computer science whether non-deterministically polynomial problems can be solved in polynomial time. I am curious to know what makes this ...
9
votes
0answers
228 views

Complexity of the min edge-colored cut problem

Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V_1,V_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V_1, v \in V_2$ is ...
13
votes
1answer
459 views

Given a graph, decide if its edge connectivity is at least n/2 or not

Chapter 1 of the book The Probabilistic Method, by Alon and Spencer mentions the following problem: Given a graph $G$, decide if its edge connectivity is at least $n/2$ or not. The author mentions ...
5
votes
0answers
324 views

Complexity of balanced graph partition problem

Wagner and Wagner, in "Between min cut and graph bisection" (MFCS 1993), studied a variant of minimum bisection problem where we seek a cut with minimum size such that each partition has at least $\...
13
votes
0answers
647 views

Online algorithms: open problems

Recently the long-standing k-server problem has been solved by Nikhil Bansal, Niv Buchbinder, Aleksander Mądry and Seffi Naor (to appear in FOCS 2011). I'm interested in knowing other open problems in ...
15
votes
2answers
570 views

Quantum PAC learning

Background Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If ...
35
votes
1answer
980 views

Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

Recently Gil Kalai and Dick Lipton both wrote a nice article on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and Riemann Hypothesis. Conjecture. Let $\mu(k)$ be ...
25
votes
2answers
1k views

Finding a prime greater than a given bound

Is a deterministic polynomial-time algorithm known for the following problem: Input: a natural number $n$ (in binary encoding) Output: a prime number $p > n$. (According to a list of open ...
13
votes
2answers
2k views

What are current open problems in compiler theory?

Compiler theory seems to be a pretty vetted subject. What are some open problems or current research happening in the field?
13
votes
2answers
2k views

Space-time tradeoff and the best algorithm

Consider some language $L$ such that: $L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$ and so that $L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$ In other words, the fastest machine $M$ computes $L$ ...
22
votes
2answers
1k views

Protocol partition number and deterministic communication complexity

Besides (deterministic) communication complexity $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the protocol partition number $pp(R)$. The relation between ...
22
votes
1answer
946 views

Complexity of computing shortest paths in the plane with polygonal obstacles

Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon. The Euclidean shortest path problem is to compute the Euclidean shortest path ...
5
votes
0answers
555 views

Contained in NP and Turing-reduction from an NP-complete problem $\Rightarrow$ NP-complete under Karp reductions? [duplicate]

Possible Duplicates: Do many-one reductions and Turing reductions define the same class NPC Many-one reductions vs. Turing reductions to define NPC Let $P,Q \subseteq \Sigma^*$ be languages ...
19
votes
2answers
1k 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 ...
27
votes
0answers
609 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". ...