Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
4
votes
2answers
328 views

Nontrivial separation consequences of P!=NP

I am looking for nontrivial examples of complexity class separations that are known to follow from the P!=NP hypothesis. By a "nontrivial example" I mean that it is not just an automatic consequence ...
27
votes
0answers
622 views

The complexity of checking whether two DAG have the same number of topological sorts

This problem is highly related to the CNF one. Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No". ...
9
votes
1answer
369 views

Is there a relationship between computational complexity theory and complex systems theory?

Computational complexity theory classifies problems according to their inherent difficulty. Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the ...
12
votes
2answers
855 views

Does the existence of PH-complete problems relativize?

The Baker-Gill-Solovay result showed that the P = NP question does not relativize, in the sense that no relativizing proof (insensitive to the presence of an oracle) can possibly settle the P = NP ...
3
votes
1answer
376 views

Applications of association schemes to complexity theory and other TCS

An association scheme is defined as a pair $(V, R_0,R_1, \ldots,R_{n+1})$ of a set $V$ and relations $R_i$ on $V$ such that $(x,y) \in R_i$ implies $(y,x) \in R_i$ for all $x, y \in V$. $R_0 = \{ (x,...
15
votes
4answers
518 views

Are there known to exist functions with the following direct-sum property?

This question can be asked either in the framework of circuit complexity of Boolean circuits, or in the framework of algebraic complexity theory, or probably in lots of other settings. It is easy to ...
5
votes
2answers
618 views

Problems with mixed unary/binary inputs

As a mild follow-up to this question on alphabet sizes, let me ask about the other part of the natural numbers, i.e. $\le 2$. Clearly everyone knows about problems over a binary alphabet. Unary, on ...
28
votes
2answers
2k views

A category of NP-complete problems?

Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, ...
29
votes
3answers
2k views

coNP certificate for Graph Isomorphism

It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP ...
46
votes
5answers
1k views

Are there Conservation Laws in Complexity Theory?

Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems. Or take primality. It is easier to show composites in NP ...
14
votes
3answers
602 views

The complexity of checking whether two CNF have the same number of solutions

Given two CNF, if they have the same number of assignments to make them true, answer "Yes", otherwise answer "No". It is easy to see it is in $P^{\#P}$, since if we know the exact numbers of ...
10
votes
0answers
342 views

Gap hardness of Multi-Dimensional Cover

Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the ...
0
votes
0answers
182 views

P vs. NP via psuedo-random number generators [duplicate]

Possible Duplicate: P vs. NP and Pseudorandom Bit Generators Hello again , and thank you all for making this website a great vehicle for knowledge exchange. So my question is , are you trying to ...
7
votes
2answers
2k views

Upper bounds on the length of longest simple path in non-Hamiltonian graph?

Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs. ...
8
votes
1answer
445 views

Using game-based proofs in simulation-based proofs

Simulation-based security provides more natural and more powerful definition of security than game-based security. I have seen the simulation based approaches use the game-based proofs in-part to ...
3
votes
0answers
185 views

Simulator Efficiency versus Algorithm Efficiency

I have a question about the simulator efficiency. I am reading a group key exchange protocol which is UC-Secure (the security is proven on universal composability framework of Canetti). The proof uses ...
20
votes
5answers
1k views

Deterministic Parallel algorithm for perfect matching in general graphs?

In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. ...
18
votes
4answers
943 views

Applications of Complexity Theory

Complexity theory seems to capture something fundamental about the structure of the universe, in that it formalizes the intuitive notion that some problems are harder than others. Scott Aaronson ...
22
votes
1answer
1k views

How does the BosonSampling paper avoid easy classes of complex matrices?

In The computational complexity of linear optics (ECCC TR10-170), Scott Aaronson and Alex Arkhipov argue that if quantum computers can be efficiently simulated by classical computers then the ...
5
votes
2answers
240 views

Hardness of approximation assuming the existence of one-way functions

This question is inspired by a question posed by Shiva Kintali, Hardness of approximation assuming NP != coNP . Multiplication of two prime numbers of equal size is strong candidate for one-way ...
16
votes
5answers
880 views

Do “One Way Functions” have any applications outside crypto ?

A function $f \colon \{0, 1\}^* \to \{0, 1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm $A$, $\Pr[f(A(f(x))) = f(x)] < ...
13
votes
2answers
351 views

Evaluating the multilinearization of an arithmetic circuit?

Let $p(x_1,\ldots,x_n)$ be a multi-variate polynomial with coefficients over a field $F$. The multilinearization of $p$, denoted by $\hat{p}$, is the result of repeatedly replacing each $x_i^d$ with $...
2
votes
1answer
239 views

Hardness of geometric area minimization problem

This question is a generalized variant of: Hardness of perimeter minimization? Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded ...
7
votes
2answers
1k views

P vs. NP and Pseudorandom Bit Generators

According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove that P!=NP. ...
10
votes
1answer
221 views

Uniform hierarchy of problems that span complexity and computational hierarchies

Does anyone know of a set of problems that vary uniformly and span one of the "interesting" hierarchies of complexity and computability? By interesting, I mean, for example, the Polynomial Hierarchy, ...
39
votes
3answers
2k views

Why are mod_m gates interesting?

Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's. What's so ...
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 ...
12
votes
3answers
864 views

Edge-partitioning cubic graphs into claws and paths

Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine. Input: a cubic graph $G=(V,E)$ Question: is there a partition of $E$ into $E_1, E_2, \...
5
votes
2answers
1k views

Is the following problem NP-Hard?

I'm not expert on complexity theory and combinatorial optimization. I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete. ...
6
votes
2answers
354 views

PCPs with imperfect completeness

The traditional definition of PCPs have perfect completeness -- If $x\in L$, then the prover can give a proof on which the verifier (on reading constantly many bits) always accepts. Suppose we modify ...
29
votes
2answers
855 views

Polynomial method for complexity results

Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee ...
5
votes
3answers
414 views

Measuring the connectedness of a graph, and applying it to NP problems

I'm looking for a way to measure how interconnected a graph is. It's well known that graphs can be broken down into connected components. It seems, though, that even in the cases where the graph is ...
8
votes
2answers
620 views

Quantum PCP and hardness of simulating of Hamiltonians

I have a few questions about Quantum PCP conjecture: What is the statement of the quantum PCP conjecture? What implications would Quantum PCP theorem have for simulating of Hamiltonians? Is it ...
22
votes
1answer
786 views

How much computational power fits into a cubic centimeter?

This question is a followup on the question about DNA algorithms asked by Aadita Mehra. In comments there, Joe Fitzsimmons said, in part: [T]he radius of the system must scale proportionately to ...
10
votes
1answer
442 views

Finite One-Way Permutation with Infinite Domain

Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s ...
4
votes
1answer
1k views

Simulating Turing machines (output included) with circuits

A Turing machine with input alphabet {0,1} computes a partial or total function $f \colon \{0,1\}^* \to \{0,1\}^*$. Is it possible to construct a circuit family $\{C_n\}$ such that for an input $x$ of ...
14
votes
0answers
319 views

Linear PRAM vs Arithmetic Linear PRAM

A linear PRAM model is a PRAM model without bit operations and at least one operand of the $\times$ instruction is a constant. If in addition we require that the running time does not depend on the ...
10
votes
2answers
502 views

Complexity of hidden polygon puzzle on square grids?

Hiroimono is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle. The problem is: Input: Given a set of points on on a $n$x$n$ square grid and ...
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 ...
21
votes
4answers
1k views

DNA-algorithms and NP-completeness

What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they ...
20
votes
3answers
1k views

Survey on algorithms/complexity of linear algebra

I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with ...
13
votes
1answer
1k views

Computational Power of Neural Networks?

Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace $, it's fairly easy to ...
20
votes
0answers
492 views

Model-checking for three-variable logics and restricted structures

Denote the $k$-variable fragment of logic $L$ by $L^{(k)}$. The model-checking problem for a logic $L$ with respect to a class of structures $C$, denoted $MC(L,C)$, is the decision problem $MC(L,C)...
20
votes
4answers
822 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
809 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
16k 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 ...