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

Top Questions

0 votes
0 answers
17 views

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

0 votes
1 answer
12 views

What is region construction in timed automata?

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

0 votes
1 answer
63 views

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

5 votes
1 answer
120 views

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

2 votes
0 answers
72 views

How to implement the next type inference algorithm?

4 votes
0 answers
86 views

Languages recognized Counter DFA

0 votes
0 answers
40 views

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

2 votes
1 answer
93 views

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

1 vote
1 answer
115 views

Computational complexity and general relativity

-1 votes
0 answers
24 views

NCness of unique solution fixed dimension integer programming

2 votes
0 answers
35 views

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

0 votes
0 answers
20 views

Quantifying the cost of procedures

1 vote
0 answers
51 views

Is there any inherently ambiguous indexed language?

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?

1 vote
0 answers
49 views

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

2 votes
0 answers
54 views

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

1 vote
0 answers
60 views

Generalizing Fano's inequality

3 votes
2 answers
215 views

Classes between PH and PSPACE

0 votes
1 answer
63 views

Number of stable matchings

-2 votes
0 answers
106 views

Is this theorem correct? [closed]

-1 votes
0 answers
69 views

Theorems about integrality gap for set cover linear programs

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

4 votes
0 answers
80 views

Time Complexity of Pairwise Graph Connectedness

4 votes
1 answer
106 views
+50

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

0 votes
0 answers
60 views

What is the right notion of reduction for 2EXPTIME?

1 vote
2 answers
66 views

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

0 votes
1 answer
37 views

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

2 votes
0 answers
86 views

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

2 votes
1 answer
295 views

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

1 vote
1 answer
139 views

Complexity of "discrete-time" SAT

1 vote
1 answer
156 views

Defining normalization with respect to judgmental equality instead of reduction

0 votes
0 answers
66 views

Interactive proofs with computation bounded Merlin

0 votes
0 answers
118 views

Is orthogonal polygon with crossings count NP-complete?

-1 votes
1 answer
46 views

Flow of value lower bounded by $X$

0 votes
1 answer
51 views

Running time of SAT and other EXPTIME algorithms [closed]

0 votes
0 answers
88 views

Faster algorithm for sampling unifromly at random

-1 votes
0 answers
47 views

What would be a canonical programming language?

2 votes
0 answers
150 views

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

1 vote
0 answers
57 views

On completeness of LTL

0 votes
0 answers
19 views

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

0 votes
1 answer
173 views

What Complexity Class is this? Is this already known?

3 votes
0 answers
68 views

Solving MDPs with polytope action spaces

0 votes
0 answers
68 views

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

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?

0 votes
0 answers
53 views

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

2 votes
0 answers
128 views

Barriers and ETH, or its variants

-1 votes
0 answers
119 views

why is relativization of computational complexity so versatile?


Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.