P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

5
votes
1answer
244 views

How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?

What are the caveats one should be aware of when pursuing VP=VNP question in char 2 compared to other char? What is the current frontier in regards to this question?
1
vote
0answers
40 views

The number of edges in the ith shortest path in a directed graph

$G$ - directed graph, $n$ - count of nodes According to Eppstein's Algorithm in this paper, the ith shortest path in a digraph may have $\Omega(ni)$ edges. Anybody can explain how this estimate is ...
-3
votes
0answers
42 views

Do we take these vertices? [on hold]

I am looking at an exercise about the vertex cover. We are given the undirected graph $G=(V,E)$ with $V=[10]$ and $E=\{(i, i+1)\mid i=1, \dots , 9\}$. Before I use the approximation algorithm, I ...
4
votes
1answer
83 views

Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say ...
1
vote
1answer
61 views

Is there a linear space lower bound for streaming set equality?

Consider two streams. In each stream one string arrives at a time. A query asks: Is the set of strings that has arrived so far the same in both streams? Is there a linear space randomized lower ...
1
vote
0answers
39 views

Computing Minima of the Projection of a Binary Cube

The problem is as follows: I want to compute the minima (with respect to the canonical partial order on vectors "$\leq$") of the linear projection of the extreme points of an $n$-dimensional $\{0,1\}$-...
1
vote
1answer
53 views

Why is it impossible to work with polylog length encoding schemes for quantum circuits?

I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said: The encoding disallows compression: it is not possible to work with encoding schemes that allow for ...
8
votes
0answers
94 views

Is the infinitely-often version of Ladner's theorem known?

We say two languages $\;\;\; L\hspace{.02 in},\hspace{-0.02 in}L' \: \subseteq \: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^* \;\;\;$ agree infinitely-often with each other if and ...
-1
votes
0answers
59 views

Explicit Computational Complexity of the Shortest Weight Constrained Path Problem?

The Shortest Weight Constrained Path Problem is a known NP-Complete Problem (listed NPC in Garey and Johnson - ND30]. Thus, by definition the running time of the Problem is exponential in the worst ...
1
vote
1answer
94 views

Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. ...
5
votes
0answers
61 views

Computational depth and p-time hard instances

After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic ...
5
votes
0answers
90 views

$\text{P}^{\text{Mod}_k\text{P}}$ vs $\text{P}^{\#\text{P}}$?

$\text{Mod}_k\text{P}$ is the class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no." For constant $k$, one ...
5
votes
0answers
96 views

$\mathsf{P}$ is the closure of [finite set] under [operation between languages]

I am searching for statements of the above form, that is, asserting the existence of a finite set $F$ of languages and one or more operations $\otimes\colon \mathcal{P}(\Sigma^*) \times \mathcal{P}(\...
1
vote
1answer
174 views

Complexity of 3SAT where each pair of 3-clauses share at most one variable

Consider the variant of the 3SAT problem with the following restrictions: Each clause has 2 or 3 literals. Each pair of 3-literal clauses have at most one common variable. What is the complexity ...
4
votes
0answers
110 views

Testing for satisfiability of a system of linear equations over GF(2)

Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$. Is it easier to check satisfiability of the ...
-1
votes
0answers
32 views

How to interpret these adiabatic evolutions?

I was trying to study the adiabatic Hamiltonian defined in the paper (arXiv:1207.1712) titled 'Solving the Graph Isomorphism Problem with a Quantum Annealer'. My case is the cycle graph $C_n$ when $n$...
4
votes
2answers
135 views

Characterisation of P in terms of register machines

It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown. It is relatively straightforward to prove that indirect addressing ...
-4
votes
1answer
92 views

What is the relationship between tail recursion with other recursions? [closed]

I'm rather confused by the recursion theory. From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ...
2
votes
1answer
70 views

What is the recognition complexity of k-uniform k-partite hypergraphs? [duplicate]

We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied. It's also ...
0
votes
1answer
128 views

Paritioning a graph into clique and independent set

I am interested in the complexity of the following problems: Input: an undirected graph $G = \langle V, E \rangle$ Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $...
6
votes
1answer
105 views

Complexity of testing if a hypergraph has generalized hypertreewidth $2$

A hypergraph $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of hyperedges, i.e., subsets of $V$. The generalized hypertreewidth (GHW) parameter is a measure of the cyclicity of a ...
6
votes
1answer
574 views

States and Probability distributions that the 5-qubits IBM computer can produce

IBM has recently built a 5-qubits quantum computers based on superconducting qubits. It is even possible to make experiments over the cloud. The space of pure states for 5 qubits is the unit sphere ...
7
votes
1answer
273 views

Complexity of “destroying” the graph's minimum spanning tree weight

Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$. Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\...
2
votes
1answer
312 views

Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?

Let $M$ be a probabilistic Turing machine with a unary input $n$ whose space is bounded by a polynomial in $n$ and its output is a distribution $D$ over binary strings. Note that the number of ...
5
votes
1answer
182 views

Algorithm/Complexity for the following SAT Version

Given : A 3 SAT problem. Known 1 : The SAT problem is satisfiable. Known 2 : We have a solution that satisfies the given 3 SAT. Problem Statement: Maximize the solution, i.e. find a solution such ...
0
votes
0answers
49 views

Identity testing of margins of boolean functions

Consider a boolean function $f(\vec{x},\vec{y})$, we define an (integer-valued) function $g(\vec{x})=\sum_{\vec{y}}f(\vec{x},\vec{y})$, i.e., $g$ can be considered as a (sort of) margin of $f$. The ...
9
votes
0answers
162 views

reference request: deciding validity of higher-order quantified boolean formulas is not Kalmar-elementary

$\newcommand\iddots{⋰}$In "A simple proof of a theorem of Statman" (TCS 1992), Harry Mairson gives a simple proof of Statman's result that deciding $\beta\eta$-equality of terms in simply typed lambda ...
1
vote
0answers
36 views

About increasing the objective values of certificates for Max-Clique SDP

Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and ...
4
votes
0answers
63 views

Graph Isomorphism of Strongly Regular Graph with fixed parameter

$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant. Here, $n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
3
votes
0answers
173 views

On the permanent mod $p$

Computing the permanent $\bmod p$ of an $n\times n$ $0/1$-matrix is $\#P$-complete if $p$ is a prime $p>n$. We have an FPTAS for approximating the $0/1$ integer matrix permanent over the reals. ...
-6
votes
3answers
97 views

Fixed parameter tractability [closed]

Lets say I have an algorithm with complexity $O(n^k)$ where $n$ is the size of the input and $k$ is a parameter. Clearly this is superpolynomial; but in fixed parameter tractability we restrict $k$ to ...
4
votes
1answer
183 views

Binary rank of binary matrix

Let $M$ be a binary ($0-1$) matrix of size $n \times m$. We define binary rank of $M$ as the smallest positive integer $r$ for which there exists a product decomposition $M = UV$, where $U$ is $n \...
4
votes
0answers
50 views

Combinatorial characterization of hypergraph Tseitin satisfiability

The Tseitin formulas are as follows: Given a connected graph and a function $\alpha: V \rightarrow \{0,1\}$. Associate each edge $e$ with a variable $x_e$. The Tseitin formula $G(\alpha)$ is defined ...
1
vote
0answers
72 views

Counting points on curves

It is known (see "Counting curves and their projections" (free version) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of $\mathbb{F}_q$-rational points on a ...
6
votes
0answers
170 views

Testing Isomorphism of projective planes

Miller showed that isomorphism testing of projective planes can be done in $v^{O(\log \log v)}$. I would like to know whether Babai's techniques that led to the quasipolynomial time algorithm for GI ...
0
votes
1answer
175 views

Complexity of $r$-sum as a function of integer sizes

Given $n$ distinct integers whose absolute value is of size $c_{n,k}=\lceil n^{1/k}\rceil$ bits ($c_{n,k}$th bit position is always $1$ for absolute value) we know that using dynamic programming we ...
19
votes
1answer
266 views

For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

It is well known that the following problem is PSPACE-complete: Given regular expression $\beta$, does $L(\beta) = \Sigma^*$? What about determining equivalence to other (fixed) regular ...
3
votes
0answers
135 views

The complexity of the disjoint union of a sequence of complete problems

Suppose that for every $k \in \mathbb{N}$ the decision problem $A_k$ is hard for $\mathsf{N}k\text{-}\mathsf{ExpTime}$. What is the complexity of their disjoint union $A = \{ (k,x) \mid k\in \mathbb{...
10
votes
1answer
648 views

Is ALogTime != PH hard to prove (and unknown)?

Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP: Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on ...
4
votes
0answers
108 views

Beating naive dynamic programming: examples similar to integer partitions?

Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming ...
5
votes
0answers
133 views

What are problems in SC we don't know to be in NC?

NC and SC are, roughly, the class of problems decidable by shallow circuits of polynomial size and the class of problems decidable by narrow circuits of polynomial size, respectively. They are both ...
1
vote
0answers
100 views

On classes $AWPP$ and $APP$

(1) $PP$ contains problems like 'is perm(M)>k'. So what problems does $AWPP$ and $APP$ contain with respect to permanent? (2) Since it is not known if $NP$ is in $AWPP$ or $APP$ is there a candidate ...
0
votes
1answer
121 views

Evidence of containment of $PH$

We know that $PH$ is in $P^{PP}$ or in $P^{\#P}$ and we do not know if $PH$ is in $PP$. We know $AWPP$ and $APP$ are weakening of $PP$ where $AWPP$ is in $APP$ is in $PP$. (1) Is it possible if $PH$ ...
9
votes
0answers
68 views

Consequences of bipartite perfect matching not in NL?

Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$? I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be in $...
9
votes
1answer
153 views

Is a quadratic nondeterminism speed-up of deterministic computation plausible?

This is a follow up to nondeterministic speed-up of deterministic computation. Is it plausible that nondeterminism (or more generally alternation) would allow a general quadratic speed-up of ...
5
votes
0answers
60 views

Finding of dimension of algebraic varieties

I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf). Are ...
13
votes
3answers
354 views

Nondeterministic speed-up of deterministic computation

Can nondeterminism speed-up deterministic computation? If yes, how much? By speeding-up deterministic computation by nondeterminism I mean results of the form: $\mathsf{DTime}(f(n)) \subseteq \...
6
votes
2answers
356 views

Is it known whether $BPP\cap NP\subseteq RP$?

The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?
7
votes
1answer
241 views

Parity P and AM

What is known about non-trivial inclusions of $\oplus\mathsf{P}$ in other classes? In particular, is it known whether $\oplus\mathsf{P}$ is contained in $\mathsf{AM}$? The same questions apply to the ...
7
votes
2answers
174 views

Parametrized complexity of the 2-Long Paths Problem

Consider the following problem: Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $...