Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
35
votes
4 answers

Correspondence between complexity classes and logic

I took a class once on Computability and Logic. The material included a correlation between complexity / computability classes (R, RE, co-RE, P, NP, Logspace, ...) and Logics (Predicate calculus, first order logic, ...). The correlation included…
ripper234
  • 873
  • 10
  • 15
35
votes
8 answers

Alan Turing's Contributions to Computer Science

Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, undecidability, and the Turing test. However, his important…
Lev Reyzin
  • 11,968
  • 13
  • 63
  • 103
35
votes
11 answers

Approximation algorithms for problems in P

One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for several reasons. Off the top of my head, an…
aelguindy
  • 951
  • 7
  • 15
35
votes
2 answers

NTIME(n^k) ≠ DTIME(n^k) ?

In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that $\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$. This answers my question with k=1. Is anything known…
Bruno
  • 4,449
  • 33
  • 45
34
votes
3 answers

Comparison-based data structure for finding items

Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$? I really think there isn't, so a proof that…
Chi-Lan
  • 443
  • 3
  • 6
34
votes
2 answers

How did TCS become conference-oriented rather than journal-oriented?

Disclaimer: I can only vouch for my research fields, namely formal methods, semantics and programming language theory. The situation is possibly different in other parts of the discipline. It seems that TCS has become rather conference-oriented.…
Ohad Kammar
  • 2,677
  • 23
  • 28
34
votes
5 answers

Fast Reduction from RSA to SAT

Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention: Build a public library of 3SAT instances, with as few variables and clauses as possible, that would have…
Huck Bennett
  • 4,868
  • 2
  • 33
  • 46
34
votes
3 answers

Is Descriptive Complexity dead?

I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be Neil Immerman's book, but this is already quite…
Noel Arteche
  • 988
  • 6
  • 12
34
votes
2 answers

Does LOGLOG = NLOGLOG?

Define LOGLOG as the class of languages which can be computed in space O(loglog n) by a deterministic Turing machine (with two-way access to the input). Similarly define NLOGLOG as the class of languages which can be computed in space O(log log n)…
domotorp
  • 13,931
  • 37
  • 93
34
votes
5 answers

Evidence that PPAD is hard?

There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "surprising" consequences (like the collapse of the…
Aaron Roth
  • 9,870
  • 1
  • 43
  • 68
34
votes
5 answers

The unreasonable power of non-uniformity

From the common sense point of view, it is easy to believe that adding non-determinism to $\mathsf{P}$ significantly extends its power, i.e., $\mathsf{NP}$ is much larger than $\mathsf{P}$. After all, non-determinism allows exponential parallelism,…
Andras Farago
  • 11,396
  • 37
  • 70
34
votes
6 answers

Why are so few natural candidates for NP-intermediate status?

It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates for this status, such as Graph Isomorphism, and a…
Andras Farago
  • 11,396
  • 37
  • 70
34
votes
3 answers

Hardest known natural problem in P?

I wonder, what is (currently) the largest number $k$, such that a natural problem is known with the following properties: An $O(n^k)$ algorithm has been already found for the problem. For any fixed $\epsilon>0$ no $O(n^{k-\epsilon})$ algorithm is…
Andras Farago
  • 11,396
  • 37
  • 70
34
votes
3 answers

Is $AC^0/poly \cap NP$ contained in $P$?

I thought I would share this question as it might be interesting for other users here. Assume that a function which is in a uniform class (like $NP$) is also in a small nonuniform class (like $AC^0/poly$, i.e. nonuniform $AC^0$), does this imply…
Kaveh
  • 21,577
  • 8
  • 82
  • 183
34
votes
2 answers

Reference for NP-hardness of 3-colouring?

I have a historical question. I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard. The tempting answer is “Karp’s original paper”, but that is wrong.…
Thore Husfeldt
  • 780
  • 6
  • 11
1 2 3
…
99 100