Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

0
votes
0answers
18 views

Any Natural Problems shown Easy by Reduction to Horn SAT?

To show that a problem is polynomial-time solvable, an often-successful technique is to reduce it to 2SAT (that is the problem of deciding satisfiability of CNF formulas with every clause containing ...
1
vote
1answer
30 views

Does removal of unit production from the grammar may increase number of total production?

I have doubt ! Problem is There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions) (a) O(m) ...
3
votes
1answer
27 views

Prove or disprove that $NL$ is closed under polynomial many-one reductions

If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$. Prove that the above claim is correct, incorrect, or equivalent to an open ...
3
votes
0answers
32 views

Minimum edge deletion partitioning of a planar graph

I'm interested in the time complexity of the following problem: Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
1
vote
1answer
50 views

NP-hardness reductions

Suppose I have two generic problems $A_{1}$ and $A_{2}$: the instance of $A_{i}$ is a graph $G$ and a number $t$, and the question is whether a certain parameter $P_{i}(G)$ is at least $t$. Suppose ...
2
votes
1answer
43 views

Example of reduction in communication complexity

Let us assume the standard situation in communication complexity with two players $P_1,P_2.$ We have a function $f:[n] \times [n] \mapsto \{0,1\}$ that both players known in advance. They wish to ...
1
vote
1answer
27 views

Prove that $coRP \subseteq RP^{RP}$

I've read in an article that $coRP = RP$ is an open question, but that it is obvious that $coRP \subseteq RP^{RP}$. If $L \in coRP$, I don't understand how access to the oracle helps to build a ...
1
vote
0answers
19 views

Inherent complexity of testing line segment intersections with aligned and oriented bounding boxes?

It is well known that in practice, a substantial difference in run-time between algorithms for testing intersection of a line segment with aligned or oriented bounding boxes (in computer graphics ...
2
votes
1answer
58 views

Implications of $NP = \Sigma_2 P$ for PH collapse

A simple fact is that $P = NP \to P = coNP$, which follows from the observation that $P$ is closed under complement. I am having trouble seeing that an analogous statement is true at higher levels of ...
3
votes
2answers
99 views

Is my theorem about $P \neq NP$ correct? [closed]

It is known that there are problems in P that, provably, are not solvable in less than $O(N^k)$, for some $k$. Now consider some infinite set $K \subseteq \mathbb{R}^+_0$ such as K is unbounded from ...
3
votes
1answer
68 views

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets: If the set resulting from the union, intersection, or Cartesian product of two ...
5
votes
2answers
141 views

Complexity of “given a graph $G$ with vertex $v$, is there a maximum clique containing $v$”?

The usual way of translating the maximum clique problem into a decision problem is to ask "does there exist a clique of size $\ge k$ in $G$?" Clearly this problem is in NP (and is NP-hard). Another ...
0
votes
1answer
64 views

Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$?

If $\mathsf{NP\subseteq BPP}$, then we know that $\mathsf{NP\subseteq RP}$ (http://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf). Does $\mathsf{NP\subseteq BPP}$ also imply ...
10
votes
1answer
282 views

Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
-3
votes
0answers
10 views

recurrence relation complexity analysis [duplicate]

I want to find time complexity of recurrence relation without using masters theorem : T(n) = 3T(n/2)+n^2.could you please help me to do so without using master theorem?
4
votes
0answers
32 views

One way communication complexity lower bounds techniques

I have been teaching myself communication complexity. I am starting to understand the general methods for proving randomized lower bounds. However, I don't yet understand what techniques are ...
1
vote
2answers
92 views

If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
1
vote
1answer
30 views

Are non-trivial sets formed by set operations on NPC sets still in NPC?

I know that from this answer to a question on the class NPC, that NPC is not in general closed under intersection and union. However, the answer used languages which form trivial languages under ...
3
votes
0answers
53 views

Complexity for finding zeroes of sum of cosines

Consider the following equation with variable $n \in \mathbb{N}$: $$\sum \limits_{i=1}^{k} \cos(n\theta_{i}) = 0.$$ Given $\theta_1,\dots,\theta_k$, I'd like to determine whether there exists $n \in ...
4
votes
2answers
111 views

Minimum edge deletion partitioning

I'm interested in the time complexity of the following problem: Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the ...
2
votes
1answer
92 views

How are these problem variants that ask about the size of optimal solutions in NP?

I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here. On page 5 (23 in the pdf), it says that the following decision problems are in NP: Is the ...
2
votes
0answers
39 views

Hardness of approximation for Disjoint Group Steiner Tree

Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group? The (intuitive) ...
9
votes
2answers
608 views

Why do we say that polynomial time is easy? [duplicate]

For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so. ...
-1
votes
0answers
45 views

How can I prove that scheduling problem F2//Lmax is NP-Hard?

I'm trying to solve it via reduction to the 2-Partion problem. All online resource are leading to a single solution, which is: http://i.imgur.com/mkPrCzb.png (taken from ...
2
votes
0answers
34 views

Relations between P^#P, NP^#P and (CO-NP)^#P

I was wondering if there were relation between the complexity classes $P^{\#P}$, $NP^{\#P}$, $(Co-NP)^{\#P}$ ?(except the trivial inclusions) I've the feeling that when taking a $NP^{\#P}$ machine, ...
2
votes
1answer
17 views

A question about the polynomial hierarchy

Why does $\Pi_i^p \subseteq \Sigma_i^p$ imply $\Pi_i^p = \Sigma_i^p$?
1
vote
1answer
54 views

Problem in Papadimitriou's “Computational Complexity” seems odd

I am studying (on my own, this is not homework) Papadimitriou's "Computational Complexity" textbook, 1st edition. On page 66, we have: 3.4.1. Problem: For each of the following problems involving ...
5
votes
1answer
51 views

Complexity of black box satisfiablty

Say I have a black box $f : 2^n \to 2$ and I want to determine if it is satisfiable. That is, does there exist an input how which it returns true. I am for the purposes of this considering $n$ to be ...
3
votes
1answer
26 views

What can a quantum query to a function do?

The $n$-qubit Hadamard gate acts as, $$H (\otimes^n \vert 0 \rangle ) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in ...
7
votes
1answer
113 views

Find the central point in a metric-space point set, in less than $O(n^2)$?

I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I ...
1
vote
1answer
60 views

Good characterization of unsatisfiable Horn3SAT formula?

Horn3SAT is $P$-complete problem under logspace reductions. Since Horn3SAT is in $P$ its complement must have short witnesses. I am looking for natural short proof that a Horn3SAT formula is not ...
0
votes
1answer
20 views

Binary tree algorithm asymptotic analysis problem

Assume we have a perfectly balanced Binary tree. We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child ...
1
vote
1answer
33 views

How to turing reduce equivalent languages $Q$ to infinite language $I$

Given two languages: $Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$ $I= \{\langle M \rangle \mid \;\vert L(M) \vert = \infty \}$ I'm trying to Turing reduce $Q$ to $I$ ...
2
votes
1answer
69 views

Proof by Turing Reduction

I need to proof the following by turing reduction. Given two languages: $Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$ $I= \{\langle M \rangle \mid \;\vert L(M) \vert = ...
4
votes
1answer
293 views

Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?

Let $\mathrm{L} \in \mathrm{NTIME}(n^3)$. Since $\mathrm{NTIME}(n^3) \subseteq \mathrm{NP}$, we have that $\mathrm{L} \le_p \mathrm{3SAT}$. However, $\mathrm{3SAT} \in \mathrm{NTIME}(n)$. Hence, ...
7
votes
2answers
63 views

Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?

The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time. $$LIN \subseteq P$$ Since HORN-SAT is solvable in $O(n)$ (as ...
0
votes
1answer
94 views

Clique decision problem restricted to a subgraph [closed]

I know that the clique problem is NP-complete. However, what if we change the problem a little bit? For example, Given a graph $G(V,E)$, an integer $k$ and a subset $S$ of $m$ vertices, we are ...
4
votes
0answers
43 views

Proof that P is closed against switching between polynomially related encodings

Lemma 34.1 Let $Q$ be an abstract decision problem on an instance set $I$, and let $e_1$ and $e_2$ be polynomially related encodings on $I$. Then, $e_1(Q)\in \mathrm{P}$ if and ...
2
votes
1answer
33 views

Are there other interpretations of |G| than |V|, that is |V(G)|?

This may be a basic question, but I'm hoping someone can settle this nagging doubt I'm having. I'm reading up on FPT complexity using a book by Downey and Fellows. It has some introductory examples ...
1
vote
0answers
24 views

How does one calculate the block-sensitivity of a function?

I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity". Can someone kindly ...
1
vote
1answer
23 views

Shaefer's Dichotomy Theorem [duplicate]

Could you please resolve a confusion with Schaefer's theorem for me? Namely, why does it not imply many problems in P are NP-complete? For example, primality testing surely cannot be reduced to one of ...
3
votes
0answers
58 views

“Balancing” positive and negative literals in 2-sat

I saw in an answer to this post that it is possible to construct 3-sat clauses with extra variables such that the number of positive and negative literals for each variable are equal. Does anyone ...
2
votes
0answers
30 views

Complexity of cubic graph decomposition

I am aware that deciding the existence of decomposition of a cubic graph into edge disjoint claws is polynomial time solvable. What is the complexity of deciding the existence of decomposition of ...
0
votes
0answers
42 views

Existence of randomized reduction but no deterministic reduction

What is the consequence to complexity theory of having a randomized reduction from an NP-complete problem to problem $\Pi$ while there is no deterministic reduction from an NP-complete problem to ...
2
votes
1answer
81 views

Complexity of a SAT related problem

Given a set of (propositional) formulae $\Phi$, two formulae $\phi$ and $\xi$, determine whether there exists $\Psi\subseteq \Phi$ such that $\Psi\models \phi$ and $\Psi\not\models \xi$. Question: ...
3
votes
1answer
25 views

P/Poly class - undecidable lanauge

I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class, a turing machine M accepts language L with advice $ {a_n} $ if: M(x,$ a_|x| ...
0
votes
1answer
47 views

Reduction of SUBSET-SUM to SET-PARTITION [duplicate]

There is a similar question that has been asked, but my question addresses particular detail of an answer. I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description: ...
3
votes
1answer
34 views

Question as regards a proof of the Time Hierarchy Theorem

I'm referring to the proof outlined here (and wikipedia.org): https://proofwiki.org/wiki/Deterministic_Time_Hierarchy_Theorem In my understanding, if I relaxed the conditions such that $K$ decides ...
1
vote
1answer
27 views

Complexity of finding these original parameters

I am given (or rather, generate randomly) three positive integers $a, b, c$. I want to know if there exist integers $m \ge 2, s \ge 1$ such that $ms+m = a, ms+1 = b, 2s+1 = c$. If there are multiple ...
3
votes
1answer
66 views

Fast algorithm for clustering groups of elements given their size/time

I don't know if there is a canonical problem reducing my practical problem, so I will just try to describe it the best that I can. I would like to cluster files into the specified number of groups, ...