P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

0
votes
0answers
4 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 ...
-2
votes
0answers
85 views

What are the fields for students inclined towards theory in computer science? [on hold]

I am highly confused about what to do in theoritical computer science? It is extremely frustrating. I keep "googling" the whole day, but everything I read about affects me, I start to like it. I just ...
4
votes
0answers
44 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 ...
-4
votes
0answers
56 views

P vs EXP (Can anybody help me where my proof should have failed?) [on hold]

First things first... I am not a mathematician that is why you may find the paper as "having not enough rigor as much as it had to have". Second, I tried to combine the basic informations on set ...
2
votes
0answers
110 views

On permanent mod $p$

Permanent of $0/1$ $n\times n$ integer matrix $\bmod p$ is $\#P$-complete if prime $p>n$. We have FPTAS for $0/1$ integer matrix permanent over reals. Moreover we can obtain $n\times n$ $0/1$ ...
-6
votes
3answers
73 views

Fixed parameter tractability

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
146 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
31 views

Is there any problem which is in NP but not a NPC and NPH? [closed]

I just started learning Complexity theory. And I am searching from the last four five days, only one thing. Is there any problem which is in NP but not a NPC and NPH. Look in this diagram, Ther is ...
-2
votes
0answers
54 views

incremental knapsack

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario. Let D be my data set which is not ordered and ...
-5
votes
0answers
63 views

NP-Complete computation complexity [closed]

Suppose X1 is NP-Complete & and X1 can be reduced to X2 in exponential time. What can we sat about the computation complexity of the problem X2? Is X2 consider NP-Hard? I know that when a problem ...
4
votes
0answers
49 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 ...
0
votes
0answers
79 views

Finite objects for which isomorphism is NP-hard or harder? [closed]

Crossposted from MO where answer didn't convince me and IMHO there are contradictory comments of high reputation users. Are there finite objects for which deciding isomorphism is NP-hard or harder? ...
1
vote
0answers
70 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
165 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
170 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
257 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 ...
10
votes
1answer
635 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
100 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
129 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
votes
0answers
122 views

On counting class $\oplus P$

If a counting problem $\Pi$ is $\#P$-complete (call $\Pi_2$) then guessing output modulo $2$ of $\Pi$ is in $\oplus P$. Assume the decision version $\pi$ of $\Pi$ is in $P$. Is there a characteristic ...
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
119 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
65 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 ...
9
votes
1answer
151 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
56 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
345 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
342 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
235 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
165 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 ...
9
votes
0answers
170 views

Monotone circuit complexity of matroids?

Call a monotone boolean function $f$ a matroid function if its minterms are bases of some matroid. I am interested in monotone circuit complexity of such functions, even when we "tie hands" of these ...
1
vote
1answer
187 views

Is finding an optimal solution to this Knapsack-like problem NP-hard?

Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $ \sum_{i=1}^{n} p_i(1-x_i)+\alpha_i ...
13
votes
0answers
280 views

Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

In a read-twice opposite CNF formula each variable appears twice, once positive and once negative. I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of ...
2
votes
0answers
134 views

Derandomization of Polynomial Identity Testing

There are some theorems that state $P = BPP$ if some condition is satisfied. For example, a theorem of Impagliazzo and Wigderson states tha $P=BPP$ unless $DTIME(2^{O(n)})$ has sub-exponential ...
3
votes
3answers
115 views

Canonisation of boolean matrices under row and column permutations

Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows: $A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, ...
4
votes
0answers
76 views

Graph partition with weighted vertices and edges

I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from ...
13
votes
1answer
675 views

Rabin's “degree of difficulty of computing a function, and a partial ordering of recursive sets”

I am looking for: Michael O. Rabin, "Degree of difficulty of computing a function, and a partial ordering of recursive sets", Hebrew University, Jerusalem, 1960 Summary: “We attempt to measure ...
5
votes
1answer
195 views

The Average-case Complexity of Simplex Algorithm

I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did ...
0
votes
0answers
104 views

Arithmetic complexity of matrix powering with non-commutative entries

Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables with $x_i$ being non-commutative. What is the complexity class and circuit and formula complexity of ...
9
votes
0answers
231 views

Checking whether two quadratic equations have a common zero

Given two quadratic equations (with integer coefficients): $x^T A_1 x+ b^T_1 x + c_1=0$ and $x^T A_2 x+ b^T_2 x + c_2=0$ The problem is to decide whether they have a common zero. Here $x$ is a ...
1
vote
1answer
165 views

Packing sets to maximize overlap

For a set of sets $A$, let $\cup A := \cup_{S \in A} S$. Consider the following problem: Input: a list of $m$ weights $w = (w_1, \ldots, w_m)$, a list of $n$ distinct subsets $T = (S_1, \ldots, ...
3
votes
0answers
116 views

About lower bounding the sample complexity of a distribution

Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" ...
1
vote
1answer
109 views

Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such ...
15
votes
3answers
463 views

Examples of successful derandomization from BPP to P

What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)? The only example that comes ...
3
votes
1answer
163 views

Zero of a multivariate cubic equation

Given a multivariate cubic equation $f(\vec{x})$ over reals where all coefficients of $f$ are integers, and a hyper-rectangle $B=\bigwedge_i x_i\in[a_i, b_i]$ where $a_i, b_i$ are constant integers, ...
6
votes
0answers
142 views

When will an NP-complete language remain hard if half of a witness is revealed with the instance?

Let $L$ be an NP-complete language. Let $W(x)$ denote the set of (polynomially length bounded) witnesses that certify $x\in L$. That is, $x\in L$ if and only if there exists a $w$, such that $w\in ...
1
vote
0answers
115 views

Complexity of counterexample function and bounded arithmetic

Let $\{L^c_i\}_{i}$ be an efficient enumeration of languages in $DTime(2^{n^c})$, e.g. clocked TMs. Assume $EXP\not = NEXP$. Let $L$ be an $NEXP$-complete language and therefore not in $EXP$. There ...
8
votes
0answers
108 views

Recognition of a primitive root

Adleman and McCurley published a paper in 1994 called "Open problems in number theoretic complexity, II" (http://ww.cstheory.com/papers/open.ps.gz) Problem 18 of this list of open problems is about ...
8
votes
1answer
166 views

Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT

Stated briefly, my question is: is Karp's original proof reducing SAT to 3SAT unnecessarily elaborate? The details are as follows. In his 1972 paper Reducibility Among Combinatorial Problems, Karp ...
6
votes
1answer
125 views

Does k-PATH admit a constant approximation?

In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$. A $\alpha$-approximation for $k$-PATH is an ...