Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
16
votes
1answer
529 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
1k 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 ...
41
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
495 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
862 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
269 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
846 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
671 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
557 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$ ...
13
votes
1answer
500 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-...
47
votes
5answers
7k 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 ...
12
votes
2answers
1k 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
538 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 ...
14
votes
2answers
446 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
426 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 ...
6
votes
5answers
3k 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
218 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, see ...
30
votes
3answers
2k 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
521 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
231 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
560 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 ...
21
votes
1answer
1k 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
469 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
1k 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 ...
7
votes
3answers
871 views

Non-rooted MST of directed graph

I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the ...
43
votes
3answers
3k views

What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

Background The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
13
votes
2answers
1k views

Counting solutions of Monotone-2CNF formulas

A Monotone-2CNF formula is a CNF formula where each clause is composed by exactly 2 positive literals. Now, I have a Monotone-2CNF formula $F$. Let $S$ be the set of $F$'s satisfying assignments. I ...
10
votes
2answers
647 views

Approximating non-trivial graph automorphism?

Graph automorphism is a permutation of graph nodes that induces a bijection on the edge set $E$. Formally, It is a permutation $f$ of nodes such $(u,v)\in E$ iff $(f(u),f(v))\in E$ Define an ...
13
votes
1answer
521 views

Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?

Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S. Instance: A permutation p in P. Question: Does there exist a graph g in ...
2
votes
1answer
4k views

Difference between NP-Hard and NP-Complete [closed]

Can someone please summarize the exact difference between NP-Complete and NP-Hard problems in simple language? Wiki and my standard books aren't exactly helping.
27
votes
6answers
2k views

How are real numbers specified in computation?

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...
29
votes
1answer
1k views

Are there canonical non-relativizing techniques?

In a lot of domains, there are canonical techniques which everybody working in the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of not ...
6
votes
2answers
5k views

What techniques are used for proving algorithms optimal? [duplicate]

Possible Duplicate: Problems that can be used to show polynomial time hardness results Given a polynomial time algorithm, what techniques are known for proving that an algorithm is optimal? E.g.,...
29
votes
3answers
2k views

A decision problem which is not known to be in PH but will be in P if P=NP

Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, the answer to this question turned out to be “yes” in a way which I had not ...
19
votes
2answers
1k views

Can we decide whether a permanent has a unique term?

Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne \...
26
votes
3answers
2k views

Consequences of #P = FP

Which would be the consequences of #P = FP? I'm interested in both practical and theoretical consequences. From a practical point of view, I'm particularly interested in consequences on Artificial ...
6
votes
2answers
595 views

When is Ising partition function easy to compute?

Consider Ising model on graph $G$ with uniform coupling strength $J$ and magnetic field $h$. I say its partition function $Z$ is easy to compute if $Z$ can be deterministically computed to arbitrary ...
21
votes
3answers
929 views

Limits to Parallel Computing

I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject: http://en.wikipedia.org/wiki/NC_%28complexity%29 The ...
4
votes
2answers
250 views

Complexity of linearized Ising model at 0

Suppose $Z_G(J,h)$ is a partition function of Ising model with coupling $J$ and magnetic field $h$ on graph $G$. What is the complexity of finding the gradient of Z at $\mathbf{0}$? Specifically, if $...
10
votes
1answer
307 views

CSPs with unbounded fractional hypertree width

At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (ACM citation) showed that for the class of hypergraphs $H$ with bounded fractional ...
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/...
12
votes
3answers
509 views

Hard gaps in maximum constraint satisfaction problems?

An equivalent formulation of PCP theorem is: For Max 3-SAT it is $NP$-hard to distinguish between satisfiable formulas and formulas where at most $r$-fraction of the clauses are satisfiable (for some $...
1
vote
1answer
252 views

Is the problem of finding the "all-terminal connectivity polynomial" polynomially bounded?

I want to proof whether the problem of finding the "all-terminal connectivity polynomial" of a given graph G(V,E) is checkable in a polynomial time. In order to do so I should first proof that it is ...
28
votes
3answers
2k views

Is it NP-hard to play international draughts correctly?

Is the following problem NP-hard? Given a board configuration for $n\times n$ international draughts, find a single legal move. The corresponding problem for $n\times n$ American checkers (aka ...
18
votes
2answers
852 views

A Boolean function that is not constant on affine subspaces of large enough dimension

I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension ...
5
votes
1answer
280 views

What is the size of a function?

I'm not sure whether this question should be asked on mathoverflow.com or here, but as it is in the context of computational complexity, I will ask here. Context Oded Goldreich states in his book ...
69
votes
7answers
4k views

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD). Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a ...
6
votes
1answer
510 views

The role of symmetry in geometric complexity theory?

I'm not well versed in geometric complexity theory so my question could be trivial. I understand that GCT program studies the symmetries of determinant and permanent to prove Valiant's Hypothesis: $...
12
votes
3answers
271 views

Is there a natural restriction of VO logic which captures P or NP?

The paper Lauri Hella and José María Turull-Torres, Computing queries with higher-order logics, TCS 355 197–214, 2006. doi: 10.1016/j.tcs.2006.01.009 proposes logic VO, variable-order logic. This ...

1
51 52
53
54 55
57