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
1 answer
65 views
Is there a simplex-like algorithm that can be used with a separation oracle?
0 votes
0 answers
3 views
Satisfiability and a Galois Theory Analog
4 votes
2 answers
194 views
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
1 vote
0 answers
8 views
Hardness of computing entropy of a function on uniform input distribution
-2 votes
0 answers
12 views
Show that PARITY has a uniform network of circuits of size O (n)
-2 votes
0 answers
18 views
Lattice in computer science
4 votes
2 answers
207 views
Induction-recursion in models other than $\mathbf{Set}$
23 votes
2 answers
1k views
Is finding Logspace reductions harder than P reductions?
0 votes
0 answers
19 views
SAT to k-in-3-SAT reduction
-1 votes
1 answer
71 views
Polynomially solvable 3-SAT problem instances
5 votes
2 answers
140 views
Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?
0 votes
1 answer
84 views
Why can't opaque optics form a category?
20 votes
0 answers
708 views
Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?
1 vote
0 answers
40 views
Evaluating multidimensional polynomials
Browse more Questions