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

Top Questions

Ask Question
Active 1 Bountied Hot Week Month
0 votes
0 answers
17 views

Can the witness for an NP-search problem be distinct from the item sought?

Mark S
  • 852
0 votes
1 answer
12 views

What is region construction in timed automata?

Shaull
  • 5,281
1 vote
0 answers
12 views

Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82

Agile_Eagle
  • 111
0 votes
1 answer
63 views

On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)

sebastian
  • 171
5 votes
1 answer
120 views

Can you define recursive predicates in 2nd order intuitionistic logic?

Emil Jeřábek
  • 14.9k
2 votes
0 answers
72 views

How to implement the next type inference algorithm?

Martin Berger
  • 10.4k
4 votes
0 answers
86 views

Languages recognized Counter DFA

Adalynn
  • 141
0 votes
0 answers
40 views

Polynomial GCD exact complexity in terms of degree and number of variables

Turbo
  • 12.5k
2 votes
1 answer
93 views

Exposition of categorical models of type theory from type-theoretic perspective

Neel Krishnaswami
  • 31.7k
1 vote
1 answer
115 views

Computational complexity and general relativity

WangAtChicago
  • 41
-1 votes
0 answers
24 views

NCness of unique solution fixed dimension integer programming

Turbo
  • 12.5k
2 votes
0 answers
35 views

Is there any context-free language that is inherently ambiguous as an indexed language

D.W.
  • 10.5k
0 votes
0 answers
20 views

Quantifying the cost of procedures

Ari Fordsham
  • 111
1 vote
0 answers
51 views

Is there any inherently ambiguous indexed language?

D.W.
  • 10.5k
0 votes
0 answers
26 views

What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?

John
  • 11
1 vote
0 answers
49 views

Clarification sought re Li & Vitanyi's Proof of Godel Incompleteness in Formal System F

Julian Moore
  • 111
2 votes
0 answers
54 views

Efficient algorithm for finding closest point for rotated and scaled $\mathbb{Z}_n$ lattice

fagd
  • 121
1 vote
0 answers
60 views

Generalizing Fano's inequality

learning_tcs
  • 11
3 votes
2 answers
215 views

Classes between PH and PSPACE

Ryan Williams
  • 26.6k
0 votes
1 answer
63 views

Number of stable matchings

Tassle
  • 331
-2 votes
0 answers
106 views

Is this theorem correct? [closed]

Newberry
  • 1
-1 votes
0 answers
69 views

Theorems about integrality gap for set cover linear programs

Hao S
  • 215
1 vote
1 answer
191 views

Is it proved that error rate of quantum computation is bounded by constant rather than a function dependent on time and environment by quantum theory

XL _At_Here_There
  • 1,059
4 votes
0 answers
80 views

Time Complexity of Pairwise Graph Connectedness

k-variant
  • 41
4 votes
1 answer
106 views
+50

Natural hard communication problems with both nondeterministic and co-nondeterministic complexity of $\sqrt{n}$?

domotorp
  • 13.6k
0 votes
0 answers
60 views

What is the right notion of reduction for 2EXPTIME?

Noel Arteche
  • 429
1 vote
2 answers
66 views

Examples of promise search problems that are easier than their non-promise variants?

Emil Jeřábek
  • 14.9k
0 votes
1 answer
37 views

Complexity and Applications of performing $N$ divisions with "similar" results?

D.W.
  • 10.5k
2 votes
0 answers
86 views

How far is the distance between Mahlo Universe and Mahlo Cardinal?

Ember Edison
  • 21
2 votes
1 answer
295 views

Is any computational complexity question solved by injury priority method except Post problem?

Joshua Grochow
  • 35.9k
1 vote
1 answer
139 views

Complexity of "discrete-time" SAT

Denis
  • 7,747
1 vote
1 answer
156 views

Defining normalization with respect to judgmental equality instead of reduction

Andrej Bauer
  • 26.8k
0 votes
0 answers
66 views

Interactive proofs with computation bounded Merlin

Alexey Milovanov
  • 1,695
0 votes
0 answers
118 views

Is orthogonal polygon with crossings count NP-complete?

Mohammad Al-Turkistany
  • 20.6k
-1 votes
1 answer
46 views

Flow of value lower bounded by $X$

J..y B..y
  • 2,570
0 votes
1 answer
51 views

Running time of SAT and other EXPTIME algorithms [closed]

Jake
  • 742
0 votes
0 answers
88 views

Faster algorithm for sampling unifromly at random

Shi
  • 115
-1 votes
0 answers
47 views

What would be a canonical programming language?

Meena Alfons
  • 99
2 votes
0 answers
150 views

On the number of optimal prefix-free binary codes [closed]

Riccardo
  • 21
1 vote
0 answers
57 views

On completeness of LTL

sbarra
  • 11
0 votes
0 answers
19 views

k-means (Lloyd's algorithm): How many times can cluster configurations repeat until a new one is observed?

user3848386
  • 1
0 votes
1 answer
173 views

What Complexity Class is this? Is this already known?

Bapcap
  • 39
3 votes
0 answers
68 views

Solving MDPs with polytope action spaces

Vanessa
  • 2,161
0 votes
0 answers
68 views

Resources I can use to understand homology/topology as a software engineer?

Mike Shulman
  • 667
0 votes
0 answers
24 views

How can I show that {a,b}∗ & {a,b,c}∗ are in an equivalence relation using the CBS theorem?

Sanad
  • 1
0 votes
0 answers
53 views

Are there parsers that can parse languages in more expressive grammars than context-free grammars?

daegontaven
  • 101
2 votes
0 answers
128 views

Barriers and ETH, or its variants

user3483902
  • 1,101
-1 votes
0 answers
119 views

why is relativization of computational complexity so versatile？

XL _At_Here_There
  • 1,059

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered 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.