Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore our questions

6 votes
0 answers
71 views

Certifying the promise in hard promise problems

0 votes
0 answers
117 views

Could we build PSPACE-based cryptography - more secure post-quantum?

-3 votes
0 answers
26 views

NP-hard problem between two disjoint points

1 vote
0 answers
62 views

Generalization of the Hamiltonian path problem on Grid Graphs

0 votes
1 answer
55 views

Is this edge-partitioning NP-Hard?

3 votes
0 answers
154 views

Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?

12 votes
1 answer
205 views

Complexity of 1-or-3-in-3-SAT (odd-3-SAT)

0 votes
0 answers
31 views

Hardness of finding minimal subsets that will change the maximum of a univariate polynomial

1 vote
0 answers
75 views

Hardness of maximization of a univariate polynomial (as a function of its degree)

13 votes
1 answer
738 views

What is the complexity of (possibly succinct) Nurikabe?

0 votes
0 answers
63 views

Enumerating all set covers with sets of size at most two

0 votes
0 answers
52 views

Prove that Vertex Cover is NP-Complete by reducing MaxCut to Vertex Cover

1 vote
0 answers
81 views

Complexity of n-rooks completion

3 votes
0 answers
116 views

Complexity of numerical 3-dimensional matching where the three multisets are identical

Browse more Questions