Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
28
votes
2answers
949 views

Approximate counting problem capturing BQP

In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say). Is ...
8
votes
2answers
3k views

Monotone-2SAT and Vertex Cover

The following decision problem is called k-True-Monotone-2SAT: Given a 2-CNF boolean formula $F$ that does not contain any negated variables and given a positive integer $k$, can $F$ be satisfied ...
16
votes
1answer
788 views

LogDCFL-complete problems

LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free ...
65
votes
5answers
2k views

Problems that can be used to show polynomial-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
1
vote
1answer
482 views

Complexity of two perfect matchings with minimum shared edges?

Perfect Matching problem is polynomial time solvable in general graphs. Given undirected simple graph, Is the problem of finding two perfect matching with minimum shared edges between them ...
4
votes
1answer
301 views

On Defining Probabilistic/Nondeterministic Circuits

Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit. The standard way of defining probabilistic/nondeterministic circuits ...
11
votes
1answer
453 views

Do people look at loop nestness in boolean circuits?

While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought ...
8
votes
1answer
2k views

Reducing #SAT to #MONOTONE-2SAT

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
1
vote
1answer
1k views

Removing all but a few cycles in a graph

Let problem $S$ be defined as Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the ...
19
votes
1answer
451 views

Visualizing Unique Games

How would you design a picture to illustrate the unique games conjecture? This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be ...
40
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 ...
38
votes
9answers
4k views

Optimal greedy algorithms for NP-hard problems

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
50
votes
20answers
8k views

NP-hard problems on trees

Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
11
votes
2answers
1k views

NP-complete variants of undecidable problems?

Examples of bounded $NP$-complete variants of undecidable sets: Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps} Bounded Tiling={ $(T, 1^t)$| there is ...
4
votes
1answer
435 views

Is this problem mappable to 3SAT or is it weaker than 3SAT?

Consider a variant of a satisifiability problem. Given n dimensions (n >= 3, n < 10,000 think of n as large but finite) The range of each dimension is either an interval over the integers or an ...
3
votes
2answers
520 views

Counting complexity of a scheduling problem. [closed]

Let $T={1,…,n}$ be a set of tasks. Each task $i$ has associated a non negative processing time $p_i$ and a deadline $d_i$. A feasible schedule of the tasks consists of a permutation of $n$ elements $\...
7
votes
2answers
444 views

On the class of the FNP version of the Hamiltonian Cycle problem

This post is linked to: FNP complexity class Many places say that the decision version of Hamiltonian Cycle is NP-Complete, and NP-Complete problems are those whose solution can be verified in ...
7
votes
2answers
575 views

SAT Solution Space - Definition of Cluster of Solutions

I'm looking for a formal definition of Cluster of Solutions. My current understanding is the following. Let $x$ be a boolean assignment on $n$ variables. Let $f: \{ 0,1 \} ^n \to \mathbb{N}$ be a ...
10
votes
1answer
436 views

Hardness of constrained star system problem?

A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-...
18
votes
2answers
2k views

Beginner's Guide to Derandomization

I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented. I'm new to the subject of "Derandomization," and as such, I wanted ...
4
votes
3answers
542 views

FNP complexity class

Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was http://en.wikipedia.org/wiki/FNP_(complexity) However, that isn't sufficient for me to ...
34
votes
2answers
3k 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)$. ...
14
votes
1answer
911 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
7
votes
3answers
5k views

Polynomial Time Algorithm for Graph Isomorphism Testing [closed]

"Michael I. Trofimov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs. The paper is given in arXiv. The companion website gives a proof-of-concept ...
11
votes
1answer
682 views

Time complexity analysis for Reingold's UST-CONN algorithm

What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?
49
votes
9answers
9k views

Best Upper Bounds on SAT

In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT." I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
5
votes
1answer
436 views

Comparing $\mathbf{NP}$ and $\mathbf{E}$

We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$. The complexity zoo states that $\mathbf{E}$ does not equal $\mathbf{NP}$, and cites the following ...
17
votes
2answers
877 views

Lower bounds on #SAT?

The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying ...
35
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$) ...
15
votes
6answers
492 views

Global properties of hereditary classes?

A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal. Classes of graphs that exclude a minor have nice ...
7
votes
1answer
3k views

Simple reduction to unbounded knapsack?

Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited ...
10
votes
3answers
1k views

An explicit separation between time-constructibility and space-constructibility?

Show a function $f(n)$ which is space-constructible but not time-constuctible. Is this problem related to a possible separation between complexity classes DTIME(f(n)) and SPACE(f(n))?
17
votes
2answers
2k views

Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?

In the "last paragraph" of the "first page" of the following paper: Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical ...
0
votes
2answers
920 views

Where is the error in the following P != NP pseudo-proof ?

Here is a necessarily wrong proof of $P \neq NP$ as it relativizes, but I can't find the error : Le $U$ be a universal Turing machine, whose inputs are restricted to Turing machines accepting ...
8
votes
2answers
896 views

PCP theorem and proof complexity?

It is known that if $P=NP$ then $CoNP= PCP[O(log(n)),O(1)]$. Also, it is known that $NEXP=PCP[poly(n),poly(n)]$. It appears that PCP can't tell us which natural problems are not in $NP$. I wonder if ...
8
votes
3answers
376 views

Is parametrized maximum independent clauses problem in FPT?

Parametrized maximum independent clauses problem: Input : A r-CNFSAT formula F having n variables and m clauses, k Ques : Does there exists at least k clauses such that they are mutually independent ...
8
votes
4answers
2k views

Complexity of marriage matching problem?

Suppose you have $n$ males and $n$ females. Each person has $m$ attributes. Each person indicates a set of attributes that a possible candidate should have. A matching is a set of pairs. Each pair ...
32
votes
2answers
1k views

How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?

In this guest post by Josh Grochow at the complexity weblog he reports on a recent workshop devoted to GCT that was held at Princeton in July. Several of the attendees argued that we should use GCT ...
20
votes
2answers
903 views

Relationship between symmetry and computational intractability?

The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0. However, If $k(n)=O(\log n)$ ...
39
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 ...
20
votes
2answers
994 views

$\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
17
votes
3answers
844 views

Which $AC^0$ problems are not "truly feasible"?

Neil Immerman's famous Picture of The World is the following (click to enlarge):                    &...
22
votes
1answer
455 views

Are there natural separations in the nondeterministic time hierarchy?

The original Nondeterministic Time Hierarchy Theorem is due to Cook (the link is to S. Cook, A hierarchy for nondeterministic time complexity, JCSS 7 343–353, 1973). The theorem states that for any ...
13
votes
1answer
861 views

Space-time tradeoff lower bounds

Following the discussion on lower bounds for 3SAT [1], I'm wondering what are the main lower bound results formulated as space-time tradeoffs. I'm excluding results such as, say, Savitch's theorem; a ...
2
votes
0answers
268 views

Some problems involving polynomials of public and private variables over GF(2).

Suppose there are a set of low degree (less than some degree $z$) polynomials $P_0, P_1, ..., P_k$ each of which is defined over two types of variables, red variables ${v_r}_0, {v_r}_1, ..., {v_r}_n$ ...
14
votes
1answer
2k views

What are the classic papers from the recursion theoretic area of complexity theory?

Two papers I would include are: D. Kozen, "Indexing of subrecursive classes", STOC, 1978. R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.
46
votes
4answers
4k views

Generalized Ladner's Theorem

Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
39
votes
3answers
9k 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 ...
1
vote
3answers
904 views

Complexity of a variant of the Mandelbrot set decision problem?

Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded ...
22
votes
1answer
927 views

Do all complexity classes have a leaf language characterization?

Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a ...