Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (1)

7
votes
0answers
79 views

Proof of PCP theorem

I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem". ...
0
votes
0answers
62 views

Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$? [closed]

I am trying to either prove or refute the claim mentioned in the title. Any ideas ?
0
votes
1answer
42 views

Relation between digraph and NP-Complete problem

Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance: Input: A digraph $G=(V,E)$ and ...
4
votes
1answer
158 views

Is building this tournament fixture an NP-Hard / NP-Complete problem?

I'm curious to know if this problem is NP-Hard / NP-Complete, which I believe would mean I'm unlikely to find a polynomial-time algorithm to solve it. I have written a program which randomly ...
2
votes
1answer
36 views

Proof of sum of powerset?

Is there already a worst case time complexity proof for the sum of all elements in a power set? I would assume, naively, you have to just add everything, which would run in about 2^n, where n is the ...
10
votes
1answer
141 views

Runtime bounds on algorithms of NP complete problems assuming P≠NP

Assume $P\neq NP$. What can we say about the runtime bounds of all NP-complete problems? i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal ...
1
vote
2answers
75 views

Does a polynomial-time reduction from A to B imply that B is in NP if A is?

Let f be a polynomial-time reduction of a decision problem A to a decision problem B. We know that, if B $\in$ P then A $\in$ P. Similarly, if B $\in$ NP then A $\in$ NP. However, what about the other ...
1
vote
0answers
44 views

How to do well in Computational theory courses? [closed]

I'm having a lot of trouble solving problems in my Comp Theory class. I just have no idea how to formulate arguments for certain things like proving the concatenation of two non reg langs can have reg ...
3
votes
3answers
188 views

Relationship between Las Vegas algorithms and deterministic algorithms

I'm wondering why the following argument doesn't work for showing that the existence of a Las Vegas algorithm also implies the existence of a deterministic algorithm: Suppose that there is a Las ...
5
votes
1answer
138 views

Reduce Vertex cover to SAT

I need to reduce the vertex cover problem to a SAT problem, or rather tell whether a vertex cover of size k exists for a given graph, after solving with a SAT solver. I know how to reduce a 3-SAT ...
3
votes
1answer
50 views

What is the difference between RAM and TM

In case of algorithm analysis we assume a generic one processor Random Access Machine(RAM). As I know RAM is machine which is no more efficient than the Turing machine.All algorithms can be ...
0
votes
0answers
17 views

Variants of the 3-Partition problem

The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known ...
0
votes
0answers
10 views

Show polynomial hierarchy levels closed under reduction [duplicate]

Most books assume that this is obvious, but I can't see how each $\Sigma_k=NP^{\Sigma_{k-1}}$ level in the polynomial hierarchy is closed under polynomial-time reductions. Is there something that I'm ...
1
vote
2answers
73 views

Every language that is reducible to a language in $\Sigma_i^p$ is also in $\Sigma_i^p$ . How?

The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows: \begin{align} \Sigma_{0}^{p} & := P, \\ \Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}}. \end{align} Why is every language ...
1
vote
2answers
43 views

How to represent a 0-valid boolean formula?

I read in these two papers http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf and http://people.csail.mit.edu/madhu/papers/noneed/fullbook.ps that if we ...
0
votes
1answer
96 views

Relaxed graph coloring, with penalties for assigning adjacent vertices the same color

Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in [N]$. Thus ...
2
votes
1answer
92 views

Proving NP-completeness of a graph coloring problem

Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they ...
1
vote
1answer
24 views

There is equivalence in an NP-hardness proof or not?

I want to show that some problem $P_1$ is NP-hard. I have a problem $P_2$ that is NP-complete. From an instance of $P_2$ I created in polynomial time an instance of the problem $P_1$. My question is: ...
2
votes
2answers
89 views

Hardness of mixed 3-SAT and 2-SAT formula

It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals. We can solve this ...
1
vote
2answers
52 views

Do the polynomials in “polynomial time” have integer, real or complex coefficients?

This is probably a very basic question but do the polynomials in "polynomial time" have integer, real or complex coefficients? Everywhere I looked it just says "polynomial expression". I am guessing ...
2
votes
1answer
93 views

Bin packing problem or not?

Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items): Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to ...
0
votes
0answers
54 views

Reduction from Steiner tree to minimum set cover

I am trying to teach myself complexity. I am trying to come up with a reduction from minimum set cover (given a set of items I, and a set S of subsets of I and an integer k, is there a subset S' of S ...
4
votes
1answer
108 views

Relation of Space and Time in Complexity?

I'm looking for some clarification on some concepts/facts I came across while studying for a class. I was reading the following wikipedia article. The below specific section and statement intrigued ...
2
votes
1answer
87 views

Is this NP-completeness proof correct?

I want to prove that a problem $P_1$ is NP-complete. Let say that I want to do a reduction from SAT problem. If the instance of problem $P_1$ depends on $M$ and $N$, can I specify the sturcture of ...
2
votes
1answer
97 views

Why is determining the size of a maximum independent set or a clique in P?

I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to ...
-1
votes
2answers
78 views

Recurrence Problem $T(n) = 3T(n/3) + n$ [duplicate]

My question here is dealing with the residual that I get. We are trying to prove $T(n) = 3T(n/3) + n$ is $O(n*\log n)$. So where I get is $T(n) \le cn[\log n - \log 3] + n$. So my residual is $-cn\log ...
2
votes
0answers
125 views

Difference between deterministic and nondeterministic universal turing machine

It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a ...
1
vote
2answers
61 views

Proving 2P2N SAT is NP-Complete

I hope I named this CNF Boolean sentence the correct way. The way I see it, a 2P2N is where each literal appears twice (or at most twice, but we can say twice without loss of generality). I am ...
1
vote
1answer
103 views

Does NP-Complete imply non-satisfiability?

I've seen a lot of text concerning the first NP-Complete problem, Boolean Satisfiability. I guess I'm confused concerning the language. It sounds to me as though the problem could be difficult to ...
2
votes
1answer
57 views

Reducing 3SAT to Triangle Cover Graph

The Triangle Cover Graph problem is this: Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also ...
0
votes
0answers
31 views

Deterministic subexponential algorithm for parity game [closed]

I'm styding this article: http://www.dcs.warwick.ac.uk/~mju/Papers/JPZ08-SIAMJComp.pdf and there is a step not clear for me. In particular : Can anyone help me to understand what is the ...
4
votes
2answers
169 views

Time complexity of base conversion

EDIT As requested, a single question Why can't arbitrary base conversion be done as fast as converting from base $b$ to base $b^k$ ? There is a big time complexity difference, so I am also ...
3
votes
1answer
126 views

Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays

A homework problem in my current CS class asks us to produce a comparison-based procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $k$ ...
3
votes
0answers
68 views

Is finding all valid nets of a polyhedron NP-hard?

Suppose I wanted to find all valid nets of a polyhedron. Is this kind of problem NP-Hard? My guess is that it is. If you were to increase the "complexity" of the polyhedron (maybe this is the number ...
0
votes
3answers
66 views

Big O relation between $2^n$ and $2^{2n}$

I know that: If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that $f(n) <= M*g(n), \forall n > n_0$ The other, plain English way of defining it is, If $f(n)=O(g(n))$ ...
1
vote
2answers
102 views

2 cases for P = NP

As we all know the million dollar question in Computer Science P=NP or not. I was trying to understand it and got some doubts please tell me whether I'm right or wrong N=NP in two cases Case 1: ...
6
votes
1answer
162 views

Why is this function computable in $O(n^{1.5})$ time?

My textbook says: "We define the function $f\colon \mathbb{N}\to\mathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number ...
4
votes
3answers
230 views

Why can't we flip the answer of a NDTM efficiently?

I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) ...
1
vote
1answer
33 views

NP hard relation with NP complete

If any problem P is NP complete then if there is a polynomial time reduction of P to another problem R then what can we say about R.Is it NP-hard or NP complete ? From Theory of computation of ...
1
vote
1answer
33 views

lexicographic depth-first search complexity class

It seems to me to be incorrect to say that lexicographic DFS is P-complete, since it isn't a decision problem. There is a corresponding decision problem, first DFS ordering, which is known to be ...
5
votes
1answer
69 views

Why can't you write the 2-paths problem as a max-flow problem?

This is a follow-up question to this. Consider the 2-paths problem: Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and ...
1
vote
1answer
64 views

Is this path finding problem in a 01-matrix NP-complete?

The problem: Input: An $n \times n$ matrix of 0's and 1's, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$) Output: YES if there exists a ...
3
votes
0answers
43 views

What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT?

What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT? We can use the Valiant Vazirani Therom, also found here (in more detail). Essentially, it is a randomized algorithm that ...
0
votes
1answer
79 views

What makes it so difficult to prove P =/≠ NP? — The subset sum issue [closed]

I can't understand or imagine some fact about NP-hard problems. If I understand it correctly there is only one polynomial-time algorithm needed – for whichever NP-complete problem – to ...
0
votes
1answer
25 views

How to analyse the complexity of a problem with two or more size measures

Consider this example: a problem of dimension $n$ and $m$ ($m,n$: any given integers). has a search space of size $O(n^n * m^n)$. It is clear that this problem is exponential in $n$, whatsoever $m$ ...
0
votes
1answer
17 views

Blum's speedup theorem showing unclassifiable complexity languages?

Do any of Blum's theorems prove that there exist decidable languages that are unclassifiable anywhere in the time hierarchy? In other words, asserting they (mentioned in the proofs) are computable ...
1
vote
1answer
22 views

Blum's speedup theorem in big-O format?

Is there a way to state Blum's speedup theorem in terms of Big-O (Landau) notation?
1
vote
1answer
55 views

Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?

The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in ...
2
votes
0answers
97 views

Intractable properties of Two-factor in connected bridgeless cubic graphs

Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that ...
-1
votes
2answers
41 views

Reducing 3CNF to Clique: Why do we omit negated literals?

I have an example for a reduction of 3CNF to Clique, there is one thing I don't get about it, hopefully you could clarify it. The reduction works like this: Construct a graph G = (V, E) as ...