All Questions

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

Is there a logic without induction that captures much of P?

The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ...
38
votes
3answers
8k views

Is optimally solving the n×n×n Rubik's Cube NP-hard?

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
38
votes
1answer
2k views

Prerequisite for learning GCT

It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory. While I am a CS student and do NOT have classes of very abstract ...
38
votes
2answers
3k views

Mulmuley's GCT program

It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been ...
38
votes
2answers
5k views

Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm

Is anyone familiar with Yijie Han's $O(n \log\log n)$, linear space, integer sorting algorithm? This result appears in a fairly short paper (Deterministic sorting in $O(n \log\log n)$ time and linear ...
37
votes
14answers
23k views

How practical is Automata Theory?

There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...
37
votes
6answers
2k views

Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?

A number of geometric problems are easy when considered in $R^1$, but are NP-complete in $R^d$ for $d\geq2$ (including one of my favourite problems, unit disk cover). Does anyone know of a problem ...
37
votes
4answers
3k views

Is $PH \subseteq PP$?

We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that $PP \subseteq PSPACE$. We also know from Toda's Theorem that $PH \subseteq P^{PP}$. Do we know whether $...
37
votes
7answers
6k views

What do we know about provably correct programs?

The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in ...
37
votes
5answers
1k views

When should you say what you know?

What should you do when you see a question raised in public, say here on stack-exchange, that you know the answer to, because you are looking into as part of current research project? For example, I ...
37
votes
3answers
3k views

Does $VP \neq VNP$ imply $P \neq NP$?

As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the ...
37
votes
4answers
1k views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
37
votes
5answers
1k views

Results in Theoretical CS independent of ZFC

I'm going to ask a quite vague question, since the borderline between theoretical computer science and math is not always easy to distinguish. QUESTION: Are you aware of any interesting result in CS ...
37
votes
2answers
3k views

Axioms necessary for theoretical computer science

This question is inspired by a similar question about applied mathematics on mathoverflow, and that nagging thought that important questions of TCS such as P vs. NP might be independent of ZFC (or ...
37
votes
4answers
4k views

What would you advise someone who wants to do research as a hobby?

I love doing TCS in my spare time. Lately I have been trying to do some research as a hobby. I'm looking for some extra input from people who do this full-time: - Do you think it is possible to do ...
37
votes
6answers
3k views

Grid $k$-coloring without monochromatic rectangles

Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known. Anyone feel up to trying 5-colorings? ;...
37
votes
2answers
4k views

Sum-of-square-roots-hard problems?

The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater ...
37
votes
3answers
1k views

Parameterized complexity of Hitting Set in finite VC-dimension

I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...
36
votes
13answers
2k views

Easy decision problem, hard search problem

Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete). What are some other examples of problems where ...
36
votes
6answers
13k views

Complexity of the simplex algorithm

What is the upper bound on the simplex algorithm for finding a solution to a Linear Program? How would I go about finding a proof for such a case? It seems as though the worst case is if each vertex ...
36
votes
15answers
6k views

Everyday encounters with NP-complete problems

Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap. ...
36
votes
8answers
14k views

Why go to theoretical computer science/research?

I'm currently starting on the university [computer science] and there we have lot of opportunities to begin with researching. Before finding this website, I had no intention to go on this way [I ...
36
votes
3answers
2k views

Techniques for showing that problem is in hardness “limbo”

Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this ...
36
votes
7answers
3k views

What is the oldest open problem in TCS?

This problem is inspired by this MO question, which I thought was very interesting. What is the oldest open problem in TCS? Clearly this question needs some clarification. First, what is TCS? ...
36
votes
9answers
11k views

Data for testing graph algorithms

I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
36
votes
4answers
3k views

Hardness of approximation without the PCP theorem

An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any ...
36
votes
6answers
5k views

Regular expressions aren't

Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton. For ...
36
votes
6answers
4k views

Have you ever realized you can't solve the homework you assigned?

This question is targeted at people who assign problems: teachers, student assistants, tutors, etc. This has happened to me a handful of times in my 12-year career as a professor: I hurriedly ...
36
votes
3answers
5k views

P and NP classes explanation through lambda-calculus

In the introduction and explanation P and NP complexity classes often given through Turing machine. One of the model of computation is the lambda-calculus. I understand, that all of models of ...
36
votes
3answers
889 views

Why does randomness have stronger effect on reductions than on algorithms?

It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite ...
36
votes
3answers
5k views

Extended Church-Turing Thesis

One of the most discussed questions on the site has been What it Would Mean to Disprove the Church-Turing Thesis. This is partly because Dershowitz and Gurevich published a proof of the Church-Turing ...
36
votes
8answers
2k views

Collaborative tools for dummies/professors

Suppose that coauthors from two or more different institutions are writing a paper in latex, and would like to do better than repeatedly emailing drafts back and forth. They realize they can open for ...
36
votes
6answers
6k views

Journals with quick reviewing

Background: The motivation for this question is two-fold. First, I would like to get some hard facts to better understand the ongoing conferences vs. journals debate. Second, if this information was ...
36
votes
3answers
2k views

Complexity of exponential function

We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs. ...
36
votes
3answers
2k views

Is there a backup/replacement for the Complexity Zoo?

This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close. The Complexity Zoo webpage (http://qwiki.stanford.edu/index.php/...
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
4answers
8k views

Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally: It uses O(1) space It can be updated to reflect an insertion or deletion in O(...
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
8answers
2k views

Higher-order algorithms

Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data. Some are second-order in a trivial way, for example sorting, hashtables or the map and ...
35
votes
7answers
7k views

How do I get started in theoretical CS ?

I'm a freshmen studying computer science and I already know that I want to go into academia with focus of theoretical comp sci. I already read some of papers referenced in this question and this ...
35
votes
5answers
2k views

Integer multiplication when one integer is fixed

Let $A$ be a fixed positive integer of size $n$ bits. One is allowed to pre-process this integer as appropriate. Given another positive integer $B$ of size $m$ bits, what is the complexity of ...
35
votes
3answers
4k views

Why does Coq have Prop?

Coq has a type Prop of proof irrelevant propositions which are discarded during extraction. What are the reason for having this if we use Coq only for proofs. Prop is impredicative, so Prop : Prop, ...
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
6answers
6k views

A probabilistic set with no false positives?

So, Bloom filters are pretty cool -- they are sets that support membership checking with no false negatives, but a small chance of a false positive. Recently though, I've been wanting a "Bloom filter" ...
35
votes
2answers
3k views

Semantic vs. Syntactic Complexity Classes

In his "Computational Complexity" book, Papadimitriou writes: RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
35
votes
2answers
2k views

If P=NP, could we obtain proofs of Goldbach's Conjecture etc.?

This is a naive question, out of my expertise; apologies in advance. Goldbach's Conjecture and many other unsolved questions in mathematics can be written as short formulas in predicate calculus. For ...
35
votes
4answers
2k views

What is the smallest result you publish on ArXiv?

In essence, the question is: What is the least publishable unit for the ArXiv? Of particular interest are fields that use the ArXiv extensively such as quantum computing. But comments on other ...
35
votes
7answers
1k views

Formal notion for energy complexity of computational problems

Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is ...
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 >...

15 30 50 per page