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
Theoretical Computer Science

Explore our questions

Ask Question
more tags
Active Hot Week Month
6 votes
0 answers
71 views

Certifying the promise in hard promise problems

Noel Arteche's user avatar
Noel Arteche
  • 751
0 votes
0 answers
117 views

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

Jarek Duda's user avatar
Jarek Duda
  • 325
-3 votes
0 answers
26 views

NP-hard problem between two disjoint points

Refrain's user avatar
Refrain
  • 51
1 vote
0 answers
62 views

Generalization of the Hamiltonian path problem on Grid Graphs

TRP's user avatar
TRP
  • 31
0 votes
1 answer
55 views

Is this edge-partitioning NP-Hard?

Martin Vatshelle's user avatar
Martin Vatshelle
  • 1,329
3 votes
0 answers
154 views

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

plm's user avatar
plm
  • 131
12 votes
1 answer
205 views

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

a3nm's user avatar
a3nm
  • 8,866
0 votes
0 answers
31 views

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

Amit Bergman's user avatar
Amit Bergman
  • 11
1 vote
0 answers
75 views

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

Amit Bergman's user avatar
Amit Bergman
  • 11
13 votes
1 answer
738 views

What is the complexity of (possibly succinct) Nurikabe?

David Eppstein's user avatar
David Eppstein
  • 50.8k
0 votes
0 answers
63 views

Enumerating all set covers with sets of size at most two

Balchandar Reddy's user avatar
Balchandar Reddy
  • 63
0 votes
0 answers
52 views

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

Chaithanya's user avatar
Chaithanya
  • 11
1 vote
0 answers
81 views

Complexity of n-rooks completion

Mohammad Al-Turkistany's user avatar
Mohammad Al-Turkistany
  • 20.8k
3 votes
0 answers
116 views

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

domotorp's user avatar
domotorp
  • 14k
Browse more Questions

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.