Problems known to be open in the literature and any problem that, after being posed, is decided to be open by the community.
-3
votes
0answers
60 views
Algorithm in NP for the k-coloring problem
Does a generic algorithm exist that I could implement in an application to solve the $k$-coloring problem for any $k$ colors? I understand that such an algorithm would be $NP$, I'm just having trouble ...
-5
votes
0answers
80 views
Is this on the right track to prove P vs. NP? [closed]
For your consideration:
Please review the following. My questions: Does this make sense? Is it correct? Could it prove P vs NP?
P?NP#1: Draft
Let there be two plateaus, several miles apart, where ...
7
votes
1answer
148 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 ...
7
votes
1answer
182 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
241 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 ...
7
votes
0answers
156 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 = ...
7
votes
0answers
122 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
votes
1answer
491 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
724 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
278 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 ...
2
votes
1answer
229 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 ...
-1
votes
2answers
453 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
176 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
370 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 ...
4
votes
0answers
267 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 ...
10
votes
0answers
386 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 ...
13
votes
2answers
340 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 ...
30
votes
0answers
747 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 ...
22
votes
2answers
732 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 ...
9
votes
2answers
976 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?
11
votes
2answers
664 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$ ...
20
votes
2answers
887 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 ...
20
votes
1answer
443 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 ...
2
votes
0answers
321 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 ...
0
votes
0answers
125 views
estimating building shadow areas [closed]
is it possible to calculate shadow areas of buildings or simulate shadows of buildings, using the height of the buildings and the sun angle and azimuth?
40
votes
8answers
4k 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 ...
11
votes
2answers
1k 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 ...
11
votes
2answers
411 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].
...
13
votes
0answers
240 views
Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?
Assume we want to refute an unsatisfiable CNF. We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear ...
21
votes
3answers
978 views
Is it NP-hard to play international draughts correctly?
Is the following problem NP-hard?
Given a board configuration for $n\times n$ international draughts, find a single legal move.
The corresponding problem for $n\times n$ American checkers (aka ...
29
votes
7answers
2k views
What is the oldest open problem in TCS?
This problem is inspired by this MO question, which I thought was very interesting.
What is the oldest open problem in TCS?
Clearly this question needs some clarification.
First, what is TCS? ...
14
votes
2answers
857 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:
...
36
votes
0answers
792 views
A combinatorial version for the polynomial Hirsch conjecture
Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
16
votes
2answers
594 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. ...
18
votes
2answers
889 views
Polynomial time approximation algorithms for machine scheduling: how many open problems are left?
In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
9
votes
1answer
445 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 ...
38
votes
13answers
3k 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 ...
-3
votes
2answers
605 views
At last P != NP or not [duplicate]
Possible Duplicate:
Is the recent proof that P != NP correct?
some weeks ago I heard a news that some one proof that P != NP (link1 - link2) andsome days later I heard that he was wrong (I ...
35
votes
6answers
2k views
Grid $k$-coloring without monochromatic rectangles
Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known.
Anyone feel up to trying 5-colorings? ...
30
votes
2answers
2k 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 ...
34
votes
1answer
2k 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 ...
5
votes
4answers
373 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 ...
18
votes
1answer
364 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 ...
128
votes
53answers
33k 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:
...
88
votes
9answers
6k 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 ...
