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
1 answer
65 views
Is there a simplex-like algorithm that can be used with a separation oracle?
Neal Young
  • 7,668
0 votes
0 answers
3 views
Satisfiability and a Galois Theory Analog
Steven Schaefer
  • 1
4 votes
2 answers
194 views
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
daniel pehoushek
  • 95
1 vote
0 answers
8 views
Hardness of computing entropy of a function on uniform input distribution
Nicholas Brandt
  • 11
-2 votes
0 answers
12 views
Show that PARITY has a uniform network of circuits of size O (n)
Anna96
  • 1
-2 votes
0 answers
18 views
Lattice in computer science
Sohini Mondal
  • 1
4 votes
2 answers
207 views
Induction-recursion in models other than $\mathbf{Set}$
Andrej Bauer
  • 26.2k
23 votes
2 answers
1k views
Is finding Logspace reductions harder than P reductions?
Reiner Czerwinski
  • 1
0 votes
0 answers
19 views
SAT to k-in-3-SAT reduction
J.Doe
  • 274
-1 votes
1 answer
71 views
Polynomially solvable 3-SAT problem instances
J.Doe
  • 274
5 votes
2 answers
140 views
Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?
Neal Young
  • 7,668
0 votes
1 answer
84 views
Why can't opaque optics form a category?
Szumi Xie
  • 26
20 votes
0 answers
708 views
Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?
Hermann Gruber
  • 5,404
1 vote
0 answers
40 views
Evaluating multidimensional polynomials
TLDR
  • 119
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.