All Questions

Filter by
Sorted by
Tagged with
36
votes
5answers
1k views

Complexity of testing for a value versus computing a function

In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input. For example: Evaluating the ...
36
votes
1answer
2k views

Multiplying n polynomials of degree 1

The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time. You can do $O(n \...
35
votes
9answers
2k views

Surprising Results in Complexity (Not on the Complexity Blog List)

What were the most surprising results in complexity? I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of ...
35
votes
4answers
2k views

Interactive proofs for levels of the polynomial hierarchy

We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want ...
35
votes
4answers
954 views

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, ...
35
votes
4answers
1k views

Proofs that expose a deeper structure

The standard proof of the Chernoff bound (from the Randomized Algorithms textbook) uses the Markov inequality and moment generating functions, with a bit of a Taylor expansion thrown in. Nothing too ...
35
votes
3answers
4k views

Max-cut with negative weight edges

Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find: $$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$ If the ...
35
votes
8answers
3k views

Which definition of asymptotic growth-rate should we teach?

When we follow the standard textbooks, or tradition, most of us teach the following definition of big-Oh notation in the first few lectures of an algorithms class: $$ f = O(g) \mbox{ iff } (\exists c >...
35
votes
3answers
2k views

What is the Volume of Information?

This question was asked to Jeannette Wing after her PCAST presentation on computer science. “From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge ...
35
votes
4answers
17k views

Research and open challenges in Programming Language Theory

In the spirit of some general discussions like this one, I'm opening this thread with the intention to gather opinions on what are the open challenges and hot topics in research on programming ...
35
votes
1answer
2k views

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ \...
35
votes
1answer
1k views

$BQP$ vs $QMA$?

The central problem of complexity theory is arguably $P$ vs $NP$. However, since Nature is quantum, it would seem more natural to consider the classes $BQP$ (ie decision problems solvable by a ...
35
votes
1answer
2k views

Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "...
35
votes
1answer
1k views

NP-Completeness of the decision problem for the generalized 15-puzzle

I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block). Now the ...
34
votes
17answers
2k views

Hardness jumps in computational complexity?

Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path ...
34
votes
8answers
3k views

Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
34
votes
8answers
11k views

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, ...
34
votes
14answers
6k views

Book on Probability

While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability. It seems that the authors of ...
34
votes
11answers
2k views

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 ...
34
votes
5answers
6k views

NEXP-complete problems

There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...
34
votes
6answers
3k views

Efficient and simple randomized algorithms where determinism is difficult

I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
34
votes
11answers
4k views

Concepts in theoretical CS that would be approachable ages 8-14

Guessing it's unlikely a common question, but wondering if anyone has seen material that was clearly made to address this audience in a meaningful way.
34
votes
6answers
7k views

Code in Academic Papers

In my academic career, I've read quite a few academic papers on various computer science topics. Many of which involve an implementation and some assessment of that implementation, yet I have found ...
34
votes
2answers
3k views

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 ...
34
votes
3answers
1k views

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 $\...
34
votes
3answers
2k views

Type classes vs object interfaces

I don't think I understand type classes. I'd read somewhere that thinking of type classes as "interfaces" (from OO) that a type implements is wrong and misleading. The problem is, I'm having a problem ...
34
votes
3answers
1k views

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)$? ...
34
votes
3answers
3k views

Turing Machine restrictions that render halting decidable

If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$), then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the ...
34
votes
2answers
4k views

Status of Impagliazzo's Worlds?

In 1995, Russell Impagliazzo proposed five complexity worlds: 1- Algorithmica: $P=NP$ with all the amazing consequences. 2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) ...
34
votes
2answers
2k views

Consequences of $SAT \in BQP$

As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far: Quantum computers are not known to ...
34
votes
3answers
945 views

An Anthology of Complexity Assumptions

In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue ...
34
votes
1answer
1k views

Computational complexity of pi

Let $L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \}$ (where $n$ is thought of as encoded in binary). Then what can we say about the computational complexity of $L$? It's ...
34
votes
3answers
2k views

Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in ...
33
votes
12answers
5k views

Algebra oriented branch of theoretical computer science

I have a very strong base in algebra, namely commutative algebra, homological algebra, field theory, category theory, and I am currently learning algebraic geometry. I am a math major with an ...
33
votes
9answers
2k views

Randomized algorithm that “looks” deterministic?

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness ...
33
votes
5answers
4k views

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,...
33
votes
6answers
5k views

Reverse Chernoff bound

Is there an reverse Chernoff bound which bounds that the tail probability is at least so much. i.e if $X_1,X_2,\ldots,X_n$ are independent binomial random variables and $\mu=\mathbb{E}[\sum_{i=1}^n ...
33
votes
3answers
2k views

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/...
33
votes
5answers
5k views

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 ...
33
votes
11answers
27k views

Books on automata theory for self-study

I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
33
votes
5answers
10k views

What are some good introductory books on type theory?

I'm recently studying Haskell and programming languages. Could someone recommend some books on type theory?
33
votes
2answers
4k views

Do any quantum algorithms improve on classical SAT?

Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT ) For comparison, using Grover's algorithm on a quantum ...
33
votes
3answers
2k views

complexity of greatest common divisor (gcd)

Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest ...
33
votes
5answers
2k views

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 "...
33
votes
2answers
1k views

Cohomological approach to boolean complexity

A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this ...
33
votes
6answers
7k views

What's the simplest noncontroversial 2-state universal Turing machine?

I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness. So far I've created a game state ...
33
votes
2answers
2k views

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)$. ...
33
votes
2answers
1k views

“Steve's class”: origin of SC

We "know" that $\mathsf{SC}$ is named for Steve Cook and $\mathsf{NC}$ is named for Nick Pippenger. If I'm not mistaken, Steve Cook named NC in honor of Nick Pippenger, and I was told that the reverse ...
33
votes
2answers
2k views

When does “X is NP-complete” imply “#X is #P-complete”?

Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version. Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"? Of course the existence ...
33
votes
2answers
1k views

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 ...

15 30 50 per page
1
3 4
5
6 7
227