Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

0
votes
0answers
15 views

Reduce Subset Sum to a modified knapsack problem [duplicate]

The problem looks a bit like the knapsack problem, but here the objects placed in the sack are unique and it is allowed to overflow the sack. The main goal is to see if it is possible to fill all of ...
0
votes
0answers
16 views

Reduce Subset Sum to a specific problem [duplicate]

The problem looks a bit like the knapsack problem, but here the objects placed in the sack are unique and it is allowed to overflow the sack. The main goal is to see if it is possible to fill all of ...
0
votes
0answers
35 views

Is a problem in NP if it is decided by some non-deterministic, polynomial time turing machine? [duplicate]

I am working trough the book "Introduction to the theory of computation", 3rd edition, by M. Sipser. On page 294, the book states: A problem is in NP iff it is decided by some non-deterministic, ...
1
vote
0answers
88 views

On power of $P/poly$

(1) We know that $EXP ⊄ P/poly ⇒ BPP$ is in $SUBEXP$. Does $SUBEXP ⊄ P/poly$ mean $P=BPP$ or anything close? (2) We know that if $NP$ is in $P/poly$ then $PH$ collapses to second level. What is the ...
1
vote
1answer
70 views

Complexity of Hamiltonian path and clique problem

I came across this question. If we want to check if a graph contains both Hamiltonian path and clique. Would this problem be NPC. I knew that clique contains a Hamiltonian path and both problems are ...
0
votes
0answers
47 views

Why is Battleship not in P complexity class? [on hold]

I would assume that the battleship puzzle would be NP-complete and not P because the time to calculate every possible positioning of the ships is above polynomial time. However, I don't see how I ...
3
votes
1answer
60 views

If graph isomorphism yields a polynomial time algorihtm

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
0
votes
0answers
15 views

Construct a semi decidable but not decidable set using the diagonal argument

Not using anything other than the definition of SD and D I know if A is SD, then there exists a TM M such that A = L(M), and A can be enumerated, and if A is decidable, then everything in A can be ...
-1
votes
1answer
22 views

On intersection of classes [closed]

Consider classes $\mathcal C_1$ and $\mathcal C_2$ of problems both of which are $\mathsf{NP}$-complete. Does it mean $\mathcal C_1\cap\mathcal C_2$ of problems is $\mathsf{NP}$-complete?
0
votes
1answer
22 views

Complexity classes of undecidable Turing Machines

I'm finding it difficult to find the information online and I can't find the information in my college notes but i'm wondering what complexity-class languages like Atm and Halttm (The TM that always ...
-1
votes
2answers
67 views

Is the “modular subset product” problem NP-complete?

While examining some $NP$-complete problems relating to sets of integers, a question flashed through my mind: whether the $NP$-completeness of these problems is retained when integer arithmetic is ...
-1
votes
0answers
17 views

Is Dist − NP ⊆ Avg − P a reasonable stance? [closed]

It is known that $Dist-NP\subseteq Avg-P\implies P=BPP$. So proving $Dist-NP\subseteq Avg-P$ proves $P=BPP$ which most people believe. Now my problem is if $Dist-NP\subseteq Avg-P$ a reasonable ...
-5
votes
1answer
71 views

Proving a problem is in P? [on hold]

Problem: A square in an undirected graph is a cycle of length 4, i.e. four vertices that form a cycle. Show that the problem: ...
-1
votes
1answer
36 views

Give a function that is in EXPTIME but is not in O(2^n) [closed]

Give a function that is in EXPTIME but is not in O(2^n). Thanks.
1
vote
4answers
197 views

Complexity analysis of an unsolvable algorithmic problem?

In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned ...
3
votes
1answer
44 views

What is the time complexity of Summing Triples with duplicates?

Summing Triples problem is strongly $NP$-complete as shown by McDiarmid. Summing Triples problem: Input: list of 3N distinct positive integers Question: Is there a partition of the list into N ...
3
votes
0answers
46 views

Branch and Bound running time and golden ratio

This is a follow up question to When does Branch and Bound exactly stop giving solutions for the bin packing problem After testing many instances I found out that when r = V / Vtotal <= ϕ (Golden ...
1
vote
1answer
43 views

Can the decision version of an optimization problem in NP, be in P?

It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore ...
1
vote
0answers
74 views

If NP is easy on average then does it mean P=NP?

If $NP=RP$ then $NP$ is easy on average. Then from point $1$ in abstract in http://lance.fortnow.com/papers/files/derand.pdf which says $NP$ is easy on average implies $P=BPP$ do we have ...
7
votes
2answers
118 views

If O(log n) vs O(n) is exponential what is O(1) vs O(n)?

If one refers to using an O(log n) instead of an O(n) algorithm as an exponential speedup, how would one refer the speedup ...
2
votes
0answers
46 views

Are there theoretical reasons for believing that P=NP is harder than other complexity problems?

I have a meta-complexity question: Are there reasons to believe that it is more difficult to prove P != NP than, say PSPACE != EXPTIME or BPP != BQP?
3
votes
1answer
46 views

Computing MOD_4 function using MOD_2, OR, AND, NOT gates

Define the $\newcommand{\MOD}{\text{MOD}}\MOD_q$ function from $\{0,1\}^n \rightarrow \{0,1\}$ as follows: Let $x_1,\cdots,x_n$ be the input. Then $\MOD_q(x_1,\cdots,x_n)=0$ if the number of 1's in ...
1
vote
2answers
78 views

3-SUM hardness vs lower bounds on the complexity

I've recently encountered a new (for me) notion from computational complexity theory called 3-SUM hardness which is based on the conjecture that 3-SUM problem can not be solved in ...
1
vote
1answer
38 views

How often can a linear speed sort succeed?

Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$. What kind of bounds can we place ...
9
votes
1answer
605 views

Why is NP in EXPTIME?

Is there an easy way to see why NP is in EXPTIME? It seems to me a priori conceivable that there could be a problem which requires super-exponential time to solve, but whose solution could be ...
1
vote
0answers
87 views

When does Branch and Bound exactly stop giving solutions for the bin packing problem

I wrote a branch and bound algorithm for the bin packing problem and now I would like to know when exactly it stops giving solutions in a polynomial time. I have N items (each item i has a volume ...
0
votes
0answers
21 views

Is there a complexity metric for digital circuits?

Let's say that I have a digital circuit made up of XOR and AND gates. Is there any way to describe the complexity of that circuit? I could just use the total number of gates, but gates being in ...
-1
votes
0answers
33 views

Is P = NP $\cap$ FP

We know that NP $\subseteq$ #P and that P $\subseteq$ FP. But what about NP and FP? How are these classes related? What would be the implications if P = NP $\cap$ FP. Clearly, P $\in$ NP $\cap$ FP.
2
votes
0answers
27 views

Membership problem for context sensitive languages PSPACE-complete

I have read that the membership problem for CSL is PSPACE-complete but I couldn't find the proof anywhere. So I tried it myself. Let's mark the membership problem for CSL as MEM. First I have to ...
3
votes
1answer
48 views

Verifiers equivalent classes

This is a HW question, so Im not expecting full solutions or anything, but would love some direction. Also English is not my first language, so I apologize in advance. We define a new class of ...
0
votes
1answer
96 views

Finding the mistake(s) within this “proof” of NP being closed for complement

For my classes in theoretical computer science the following proof must be shown to be wrong. However, this is the first time I am attempting myself at this topic, so I would be thankful for some ...
3
votes
3answers
43 views

Complexity of finding factors of a number

I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division: For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ ...
1
vote
1answer
36 views

PRAM with no bit operations and P vs NC

I was reading up on something called the PRAM model without bit operations. What exactly does it mean that this PRAM model cannot do bit operations? I can't find a straightforward definition ...
1
vote
0answers
64 views

Reasons against Turing machines in proof complexity?

Turing machines were very successful in computability theory where Turing used them to resolve the Halting problem. His breakthrough led to proving that many other problems are algorithmicly ...
3
votes
1answer
44 views

What does the $\leq_{\mathrm{P}}$ symbol mean?

What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?
5
votes
2answers
98 views

Recommendations for a good (rigorous) text to study Computational Complexity.

I look for a good text to learn basics of computational complexity. I've read some parts of the first two chapters of "Computational Complexity: A Modern Approach" by Boaz Barak and Sanjeev Arora, ...
3
votes
2answers
198 views

Is it admited to give the complexity of a function regarding the resulting data structure?

Assume that we have a data structure which uses $O(\log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$. The time complexity of ...
1
vote
1answer
17 views

Why closedness of complement of randomized classes imply containment of complement of contained classes?

Suppose if class $\mathcal C$ is in $PP$ or $BPP$ does it mean complement also belongs to $PP$ or $BPP$ respectively? Does it immediately follow from $PP=coPP$?
0
votes
1answer
41 views

PSPACE and DTIME $2^{cn}$

This is a HW question that I'm stuck on and was hoping for some help. we're supposed to prove that: PSPACE not equals DTIME($2^{cn}$) for every $c>0$ (or actually for the union of all $c>0$) ...
1
vote
1answer
38 views

Short certificate analogy of PH?

We know that for problems in NP if the problem is an yes version then there is a short certificate and for coNP if the problem is a no version then there is a short certificate. Is there a short ...
-3
votes
0answers
11 views

Tiling problem with n x logn grid [duplicate]

If I define the tiling problem as a function that takes as input a single row of the tiling grid filled in with elements from a subset of all possible configurations of a square with 1 of 26 ...
1
vote
1answer
20 views

About the interpretation of the SOS hardness results of the planted Max-Clique problem

One can look at these two papers http://arxiv.org/abs/1502.06590 and http://arxiv.org/abs/1507.05136 and see their main theorems. If I understand right then both these papers are talking of the ...
1
vote
0answers
20 views

Decidability Proof of $A_{Cfg}$

I am a beginner to complexity theory and I came up with the following proof of decidability of $A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$} The Turing machine ...
2
votes
0answers
32 views

Minimum cost edge disjoint paths - NP hard?

I've been stuck on this problem for a while now. Here it is: The Network Reliability Problem (NRP) is defined as follows: Given an undirected graph with $n$ vertices $v_{1}, \dots, v_{n}$, a ...
3
votes
1answer
48 views

Show Recognizing two Regular Expressions as equal is in PSPACE

If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ? What I know so far is that there are decidable ...
3
votes
1answer
41 views

Need help in a question regarding polynomial oracle reductions

Prove the following: If there is a polynomial oracle reduction from $S1$ to $S2$: a. If $S2\in\ P$ so $S1\in\ P$ b. If $S2\notin\ P$ so $S1\notin\ P$ The way I see it - If there is a polynomial ...
6
votes
1answer
122 views

Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) ...
-1
votes
0answers
42 views

Reduction of SAT to Vertex Cover

I'm trying to understand how to reduce the below circuit-satisfiability problem into a vertex-cover problem. That is, show the resulting vertex cover graph and the number of vertices to select. Anyone ...
0
votes
3answers
79 views

Size of instance after reduction

A decision problem $C$ is $NP$-complete if $C$ is in $NP$, and every problem in $NP$ is reducible to $C$ in polynomial time. Reduction means transforming an instance of one problem $A$ to an instance ...
5
votes
1answer
100 views

Implication of Berman and Hartmanis conjecture

I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture : All $NP$-Complete languages are $p$-isomorphic. Then the book says that ...