Tagged Questions

P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

4
votes
1answer
79 views

Pseudorandom generators indistinguishable by uniform deterministic adversaries

I've seen pseudorandom generators defined for nonuniform efficient adversaries, or uniform probabilistic efficient adversaries. (For example, a monograph Pseudorandomness by Vadhan (here's its draft ...
-3
votes
1answer
71 views

What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
0
votes
0answers
46 views

Complexity of scheduling jobs on arcs in a network

Consider a path consisting of 3 arcs. For each arc we are given a set of jobs $j$, specified by a release date $r_j$ and a deadline $d_j$. All jobs have unit processing time. A solution of the problem ...
18
votes
3answers
376 views

Natural NP-complete problems with “large” witnesses

The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but Are there natural NP-complete problems in which ...
-1
votes
0answers
71 views

When is counting coins NP-complete? [closed]

having a bit of an issue with this question and deciding which of these situations requires dynamic programming and which are NP-complete: All three (except the last one) ask how much goes to person ...
10
votes
1answer
166 views

What is this variant of set cover problem known as?

Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$. An incremental ...
8
votes
3answers
287 views

EXPSPACE-complete problems

I am currently trying to find EXPSPACE-complete problems (mainly to find inspiration for a reduction), and I am surprised by the small number of results coming up. So far, I found these, and I have ...
2
votes
1answer
179 views

Ackermann Function Time Complexity

Are there any known problems that have an Ackermann function time complexity lower bound?
0
votes
0answers
91 views

Approximate Hard Problem

The Unique Game is easy to solve for exact solutions, but becomes extremely difficult for approximate solutions, with no exact solution available. It is quite against of our intuition. As it is known, ...
7
votes
2answers
398 views

Are there problems for which divide-and-conquer / recursion is provably useless?

When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the ...
3
votes
0answers
114 views

Can we decide Red-blue cut problem in polynomial time?

Given a directed graph whose arcs are coloured red and blue and integers $r$ and $b$, can we decide in polynomial time whether the digraph has a cut with at most $r$ red arcs and at most $b$ blue ...
10
votes
1answer
132 views

Does ${\bf AC^0PAD} = {\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem? Recently giving ...
18
votes
3answers
403 views

What is the minimum size of a circuit that computes PARITY?

It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp. (We define size as the number of AND and OR ...
1
vote
0answers
152 views

Determine the complexity class of a language [closed]

Let $L'$ be the language containing all the pairs $(G,v)$ where $G$ is a directed graph and $v$ is a vertex in $G$ such that $G$ contains a cycle (i.e. closed walk) that contains $v$ and the number of ...
15
votes
6answers
1k views

Statements that imply $\mathbf{P}\neq \mathbf{NP}$

This is sort of an open-ended question - for which I apologize in advance. Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the ...
4
votes
0answers
110 views

Recognition problem of cycle permutation graphs

A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, ...
8
votes
0answers
271 views

Is it possible to solve perfect matching in linear time

As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft. Is it possible to solve perfect matching problem in linear time for given ...
13
votes
0answers
177 views

What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows. Is there a result comparable to the ...
4
votes
2answers
109 views

Variation on partial Set Cover with penalties

I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem: Input: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup ...
3
votes
1answer
338 views

Is DAG isomorphism NP-C

Given two directed acyclic graphs $G_1$ and $G_2$, is it NP-Complete to find a one-to-one mapping $f:V(G_1) \rightarrow V(G_2)$ such that $(v_i,v_j) \in D(G_1)$ if and only if $(f(v_i),f(v_j)) \in ...
4
votes
0answers
154 views

Is this graph polynomial known? Can it be efficiently computed?

Consider a connected simple graph $G$ with $n$ vertices and $m$ edges. View each edge $\ell$ as a transposition $t_{\ell}$ acting on the set of vertices. [To be more explicit, given an edge $\ell$ ...
6
votes
2answers
325 views

Complexity of finding even cuts for a graph

Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in ...
4
votes
0answers
112 views

Problems in dynamic algorithms in computational geometry

The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as: Dynamic ...
16
votes
2answers
281 views

Complexity of the coset intersection problem

Given the symmetry group $S_n$ and two subgroups $G, H\leq S_n$, and $\pi\in S_n$, does $G\pi\cap H=\emptyset$ hold? As far as I know, the problem is known as the coset intersection problem. I am ...
9
votes
1answer
241 views

Berman-Hartmanis Isomorphism for NP$_{\mathbb{R}}$?

Using the real-RAM/BSS model, we have the class NP$_{\mathbb{R}}$, (where a BSS is the Blum-Shub-Smale model of a computer with operations over reals). We have NP$_{\mathbb{R}}$ complete problems. ...
3
votes
1answer
178 views

Can two strings be matched as disjoint subsequences of a string?

Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a ...
10
votes
3answers
303 views

Complexity of permutation related problems

Given a group $G$ of permutations on $[n]=\{1, \cdots, n\}$, and two vectors $u,v\in \Gamma^n$ where $\Gamma$ is a finite alphabet which is not quite relevant here, the question is whether there ...
-2
votes
1answer
91 views

Finding an exactly weighted st-path in a digraph [closed]

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
18
votes
1answer
459 views

Is P equal to the intersection of all superpolynomial time classes?

Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$. It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf ...
0
votes
0answers
99 views

Complexity Book with Slides

Is there a good book on complexity theory (upper level undergraduate and/or graduate) that comes with slides prepared either by the author or by someone else (but that are specifically tailored to ...
-2
votes
1answer
52 views

Is scheduling a set of tasks on single machine in P or in NP?

Given a set of tasks $T=\{t_1,\dots,t_n\}$ and execution times between the tasks $e(t_i,t_j)$ can we find a schedule $s$ for $T$ on a single machine with makespan $m_s < d$? Assume that the ...
4
votes
0answers
194 views

$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

Stephen Smale claims in Mathematical Problems for the Next Century that $$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}.$$ Can someone sketch the argument or provide a ...
2
votes
2answers
121 views

Complexity of smooth non-linear functions

EDIT: A more straightforward way of asking this question is: does evaluating a non-linear function require performing at least one multiplication? ORIGINAL QUESTION: I have an infinitely ...
11
votes
0answers
142 views

Lower bounds for the size of nondeterministic circuits

It is known that the minimum size of $U_2$-circuits computing the parity function exactly equals $3(n-1)$. The lower bound proof is based on the gate elimination method. Recently, I noticed that the ...
12
votes
2answers
249 views

Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the Complexity Zoo for definitions. An alternative definition defines $\mathsf{W}[t]$ ...
8
votes
1answer
173 views

A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut

I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence ...
8
votes
1answer
350 views

Problem that is in P only if P!=NP

Are there any problems that are solvable in polynomial time only if P!=NP, and otherwise solvable in (say) $O(2^n)$ time? A simple example would be: If P!=NP, compute a primality test for a random ...
6
votes
0answers
468 views

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER ...
4
votes
0answers
210 views

Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$ where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), ...
22
votes
2answers
472 views

Is this variation of TQBF still PSPACE-complete?

Deciding if a quantified boolean formula such as $\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$ always evaluates to true is a classical PSPACE-complete ...
6
votes
1answer
215 views
1
vote
1answer
230 views

#P-complete problems are at least as hard as NP-complete problems

I just read J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983) and one of the first ...
12
votes
1answer
208 views

Large classes which contain LOGSPACE for which strict inclusions are unknown

The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references). Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these ...
8
votes
1answer
240 views

The exponential function over algebraic numbers

Given an algebraic number $\alpha$, I am interested in finding an approximation of $\Re(e^\alpha)$ up to a given precision, where $\Re()$ refers to the real part of the complex number. Formally, I ...
5
votes
0answers
124 views

Extensions of Affine Dispersers

A function $f\colon\{0,1\}^n\to\{0,1\}$ is called an affine disperser for dimension $d$, if for every affine subspace $S\subseteq \{0,1\}^n$ of dimension at least $d$, $f$ is not constant on $S$. This ...
4
votes
1answer
112 views

Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the ...
-2
votes
1answer
82 views

Is this NP-Hard or does a known optimal polynomial time solution exist? [closed]

Suppose we have 10 items, each of a different cost Items: {1,2,3,4,5,6,7,8,9,10} Cost: {2,5,1,1,5,1,1,3,4,10} and 3 customers {A,B,C}. Each customer has a requirement for a ...
2
votes
1answer
153 views

Time complexity of d-dimensional convex hull

Consider the convex hull problem in $\Re^d$: Input: a list of $n$ points $S$ in $\Re^d$, Output: the vertices of the convex hull of $S$. What is the best lower bound on the time complexity of ...
0
votes
0answers
123 views

proving speedup phenomenon does not apply to any open complexity class separations

Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question. the Blum speedup ...
3
votes
0answers
122 views

How powerful are weak complexity classes with powerful oracles?

I am interested in complexity classes of the form $A^{B}$, where $A$ and $B$ are complexity classes such that $A \subsetneq \mathsf{P}$ and $\mathsf{NP} \subsetneq B$ are (believed to be) true. ...