Unsolved Problems
Showing 1-4 of 4 problems
CS-002
Open
The Polynomial Hirsch Conjecture
The diameter of the graph of a $d$-dimensional polytope with $n$ facets is bounded by a polynomial in $d$ and $n$....
L3
OPG-661
Open
P vs. NP
Problem Is P = NP?...
L3
OPG-36892
Open
P vs. PSPACE
Problem Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, ...
L3
OPG-59968
Open
One-way functions exist
Conjecture One-way functions exist....
L3