Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

1
vote
2answers
63 views

What does $\cdot$ mean as a notation with complexity classes?

In the wikipedia page for Toda's Theorem, the notation $A\cdot B$ is used where $A$ and $B$ are two complexity classes, but without explanation as to its meaning. SO given two classes $A$ and $B$ ...
0
votes
0answers
17 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
18 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
39 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
95 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
74 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 ...
3
votes
1answer
84 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
20 views

If graph isomorphism yields a polynomial time algorihtm [duplicate]

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
23 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
69 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
1answer
37 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
206 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
46 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
47 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
47 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
83 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
133 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
48 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
47 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
88 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
41 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
614 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
96 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
23 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 ...
2
votes
0answers
33 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
52 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
98 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
46 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
101 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
201 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
19 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
42 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
39 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 ...
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
26 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
57 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
148 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) ...
0
votes
3answers
80 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
101 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 ...
0
votes
0answers
16 views

An example of a very hard decidable language [duplicate]

What is an example of a language, which is very hard to compute though still decidable (and preferably "simple" in terms of understandability)? The language should provably not be in $NP$, and, other ...
0
votes
1answer
78 views

Is this a proof that SET COVER is not an NP-hard problem?

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows: Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = ...
0
votes
1answer
36 views

How is the formal definition of NP-hard equivalent to this colloquial one?

Wikipedia informally describes NP-hard problems as "at least as hard as the hardest problems in NP". It then states the formal definition: "a problem H is NP-hard when every problem L in NP can be ...
2
votes
0answers
53 views

What are the simplest known algorithms to compute PI?

There are many algorithms that compute PI. Some are obviously complex, involving huge formulas and constants. Some formulas are not that complex, but involve operators such as ...