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

5 votes
1 answer
157 views

What can we do with a generic oracle (as opposed to a random one)?

-1 votes
0 answers
70 views

Proof for Upper Bound on the Size of the Sum of Rational Numbers

1 vote
1 answer
118 views

Are there any algorithms that the brain is better at solving than a regular computer? How would these be found/verified?

-1 votes
0 answers
23 views

Finding an algorithm EF[1,1] and PO division for more than two agents

1 vote
1 answer
237 views

The Complexity of Multi-Objective Optimization

0 votes
1 answer
145 views

SAT to k-in-3-SAT reduction

5 votes
1 answer
296 views

Problems complete for non-deterministic PSPACE

1 vote
0 answers
61 views

Crafting ${NP}^{\#P}$-complete problems

0 votes
0 answers
15 views

Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?

3 votes
1 answer
343 views

Intuition on Lupanov's Upper Bound on Circuit Size

-3 votes
1 answer
97 views

Can one do descriptive complexity theory using abstract state machines?

5 votes
1 answer
480 views

Can Lexicographic BFS be implemented in logspace?

2 votes
1 answer
172 views

Is counting the union of power sets NP-complete?

46 votes
0 answers
1k views

Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?

Browse more Questions