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

27 votes
6 answers
3k views

Are there NP-complete problems with polynomial expected time solutions?

4 votes
2 answers
343 views

Random self reducibility and NP

16 votes
0 answers
410 views

Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?

2 votes
0 answers
94 views

Complexity of a sum with a product

0 votes
0 answers
72 views

Parameterized intractability for Twin cover

39 votes
4 answers
3k views

Techniques for showing that problem is in hardness "limbo"

-1 votes
1 answer
51 views

Polytime reduction to factoring variant of subset sum

6 votes
0 answers
133 views

Computing Sequences with Addition Chains In pseudopolynomial time?

-1 votes
1 answer
76 views

Parameters: Twin cover and Vertex cover

0 votes
0 answers
66 views

Tractability with respect to multiple parameters

7 votes
2 answers
997 views

Computational Complexity of Computer Vision Problems

17 votes
1 answer
1k views

Ranking the Difficulty of NP Hard Problems in Practice

4 votes
2 answers
283 views

NP-hard problem which is easy on average

10 votes
2 answers
343 views

Complexity of digraph homomorphism to an oriented cycle

Browse more Questions