Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
19
votes
4answers
814 views

Examples of hardness phase transitions

Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$. One example is counting spin ...
3
votes
1answer
277 views

compressing rarely used space

So an idea I've had bouncing around for a while goes like this: suppose we have some TM that runs in possibly exponential time, and thus can use possibly exponential space. But let's say that it ...
18
votes
4answers
795 views

If P = BQP, does this imply that PSPACE (= IP) = AM?

Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking... I wondered what if Quantum Computers ...
-1
votes
4answers
2k views

Interesting variation to the subset sum problem

An interesting variation of the subset sum problem was presented to me by a friend from work: Given a set S of positive integers, of size n, and integers a and K, is there a subset R (of the set S) ...
16
votes
1answer
1k views

Meaning of P=NP? depends on space-time geometry ?

This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008. http://books.google.com/books?id=...
15
votes
3answers
1k views

Complexity of edge coloring in planar graphs

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". What is the complexity of 3-edge coloring of cubic ...
79
votes
14answers
15k views

What kind of mathematical background is needed for complexity theory?

I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
12
votes
2answers
1k views

Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$. If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\...
6
votes
1answer
152 views

Non-interesting numbers via resource-bounded properties?

There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming). This is then used to justify the argument that every number ...
1
vote
1answer
257 views

Another edge partitioning problem on cubic graphs

This question was motivated by a closely related problem An edge partitioning problem on cubic graphs Input: at most cubic graph ( maximum node degree is 3) $G=(V,E)$, a natural number $k$ Question:...
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 ...
18
votes
1answer
2k views

Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3? I know it is NP-complete for the ...
17
votes
1answer
446 views

The structure of pathological instances for simplex algorithms

As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum....
0
votes
1answer
691 views

Is $P^{\#P}=(P^{\#P})^{\#P}$ ?

Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one. More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?
3
votes
0answers
191 views

Reference Request: Oracle applications outside cryptography

Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have ...
33
votes
4answers
1k 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 ...
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 ...
5
votes
1answer
492 views

What is the running time of taking a limit?

I'm interested in finding the running time(s) for determining mathematical limits. For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$. I'd like to know more about algorithms for determining ...
25
votes
4answers
2k views

Why do equalities between complexity classes translate upwards and not downwards?

Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the ...
13
votes
3answers
747 views

Is the 3-sphere recognition problem NP-complete?

It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere is in NP, via work by Saul Schleimer in 2004: "Sphere recognition lies in NP" arXiv:math/0407047v1 [math.GT]. ...
28
votes
2answers
759 views

Tight Lower bounds on Savitch's theorem

First of all, I apologize in advance for any stupidity. I am by no means an expert on complexity theory (far from it! I am an undergraduate taking my first class in complexity theory) Here's my ...
24
votes
3answers
2k views

Hardness of approximation - additive error

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
15
votes
3answers
2k views

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

It is $NP$-hard to find a constant factor approximation of longest cycle in cubic Hamiltonian graphs. Cubic Hamiltonian graphs have at least two Hamiltonian cycles. What are the best known upper ...
6
votes
1answer
145 views

Lower Bound on the difference between uniform and prefix-free complexity

The uniform Kolmogorov complexity (also known as decision complexity) of a string $\sigma$ is defined as follows: let $\phi: 2^{<\omega} \times \mathbb{N} \rightarrow {0,1}$ be a partial computable ...
31
votes
1answer
1k views

Refereed games with uncorrelated semi-private coins

I was (and still am) really interested in the answer to this question, because this is an interesting variation on the complexity of games which hasn't been resolved, so I offered a bounty. I thought ...
16
votes
1answer
485 views

Complexity of hex with random turn order.

I've been thinking of a variant of hex, where instead of the two players making moves alternately, each turn a player picked at random makes a move. How hard is it to determine the chances for each ...
9
votes
1answer
830 views

True Bit Complexity of matrix multiplication is $O(n^{4})$

Matrix multiplication using regular (row - column inner product) technique takes $O(n^{3})$ multiplucations and $O(n^{3})$ additions. However assuming equal sized entries (number of bits in each entry ...
40
votes
3answers
1k views

A fixed-depth characterization of $TC^0$? $NC^1$?

This is a question about circuit complexity. (Definitions are at the bottom.) Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{...
0
votes
1answer
490 views

Formalized configuration of Subset sum problem Worst-case ? [closed]

Is there a formal proof of the worst-case configuration of the subset sum problem? In other words - is there a set proven to be the hardest to find a subset equals to 0 from? thanks
22
votes
2answers
794 views

Multiplicative version of 3-SUM

What is known about the time complexity of the following problem, which we call 3-MUL? Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$? This problem is similar to ...
14
votes
0answers
264 views

Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?

Assume we want to refute an unsatisfiable CNF. We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear ...
15
votes
1answer
711 views

Random monotone function

In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the ...
7
votes
1answer
646 views

Permanents - Approximation and connection to integer factorization

Given a non-negative integer matrix of size $n \times n$. If the permanent can be calculated in $n^{2}$ arithmetic operations but each operation is on word size $n^{k}$ bits for some constant $k$, ...
13
votes
1answer
461 views

Is the Witness Size of Membership for Every NP Language Already Known?

The question occurred to me when I get Dana Moshkovitz answer to another topic. Let $L$ be an NP Language, and let $R_L$ be the respective NP relation. We know that there exists some polynomial $p$ ...
12
votes
1answer
451 views

Why are these two definitions of PPAD equivalent?

The complexity class PPAD is usually defined by stating that End-Of-The-Line is PPAD-complete. End-Of-The-Line is a search problem. The input consists of a directed graph in which each node has in-...
43
votes
5answers
6k views

Is the Chomsky-hierarchy outdated?

The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the ...
11
votes
2answers
964 views

Reducing P vs. NP to SAT

The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it. ...
16
votes
1answer
500 views

Does Nisan's pseudo-random generator relativize?

Nisan proved in "Psuedorandom Generators for Space-Bounded Computation", that there exists a pseudo-random generator which "fools" space-bounded computations. Does this construction hold for every ...
13
votes
2answers
410 views

multi-party Communication complexity of “Set Partition problem”

In an application I'm considering, I need to know the communication complexity of the following problem: Given $n$, let $S$ be the set of integers from $1$ to $n$. Alice, Bob, and Carol each ...
13
votes
2answers
4k views

Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?

There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's ...
5
votes
2answers
374 views

Bit complexity of integer factorization?

Integer Factorization problem: Given integers $N, M$, find an integer $d< M < N$ that divides $N$. Is it easier to find the value of a single bit? This problem is at least as hard as integer ...
5
votes
5answers
2k views

Sorting algorithm with a complexity smaller than $n \log n$?

If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input. But if we want to encode input, we ...
3
votes
1answer
209 views

Solution Clusters and Monotone-2SAT

It is known that generic k-SAT formulas may exhibit the presence of exponentially many solution clusters. Question: Is it true also for Monotone-2SAT formulas? For the definition of cluster, ...
28
votes
3answers
1k views

How many instances of 3-SAT are satisfiable?

Consider the 3-SAT problem on n variables. The number of possible distinct clauses is: $$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$$ The number of problem instances is the ...
17
votes
1answer
482 views

Fooling arbitrary symmetric functions

A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every ...
10
votes
0answers
229 views

Statistical tests between L and LogCFL

Statistical tests are used to check whether a source of randomness is "good". Blum and Goldreich (1992) mentioned two types of statistical tests : (1) deterministic polynomial time statistical tests ...
16
votes
3answers
536 views

UGC hardness of the predicate $NAE(x_1, …, x_\ell)$ for $x_i \in GF(k)$?

Background: In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary ...
20
votes
1answer
955 views

Alternate proofs of Immerman-Szelepcsenyi theorem

Immerman and Szelepcsenyi independently proved that $NL=coNL$. Using their technique of inductive counting, Borodin et al proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to ...
10
votes
2answers
440 views

Compactly representing the solution set of a SAT instance

This question has risen in my mind after reading András Salamon's and Colin McQuillan's contributions to my previous question Counting solutions of Monotone-2CNF formulas. EDIT 30th Mar 2011 Added ...
6
votes
1answer
980 views

Is #P contained in PSPACE?

It's obvious that NP $\subseteq$ #P. How about #P $\subseteq$ PSPACE? It strikes me as semi-obvious, since we can check whether an assignment (e.g. for SAT) is a solution in polynomial time (and ...