Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

1
vote
2answers
43 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$ ...
1
vote
1answer
12 views

Heavy hitters problem linear scan and auxiliary space

I'm looking at Lecture #2 from this Stanford course http://web.stanford.edu/class/cs168/index.html, let me introduce the HH problem: We have an array of $n$ elements and we want to know which ...
1
vote
0answers
91 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 ...
0
votes
0answers
17 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 ...
22
votes
1answer
820 views

Is Logical Min-Cut NP-Complete?

Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
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
37 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, ...
51
votes
8answers
3k views

Algorithmic intuition for logarithmic complexity

I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$. In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
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, ...
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 ...
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 ...
1
vote
1answer
57 views

Reduce set partition search to decision?

I'm a little lost and don't know how to approach this problem. Show the partition search problem can be poly-time reduced to the partition decision problem, the partition decision problem takes ...
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 ...
-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 ...
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?
-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: ...
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
1answer
36 views
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 ...
4
votes
2answers
225 views

What is the time complexity of checking if a number is prime?

Could some one please explain how to get the time complexity of checking if a number is prime? I'm really confused as to if it is $O(\sqrt{n})$ or $O(n^2)$. I iterate from $i=2$ to $\sqrt{n}$ and ...
0
votes
1answer
30 views

Log reduce PATH to DISTANCE-PATH

An instance of PATH is given by where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t. DISTANCE-PATH is similar, but with an extra requirement ...
-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 ...
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 ...
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
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 ...
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 ...
10
votes
2answers
256 views

Would $\sf RP = NP$ imply $\sf NP = coNP$?

If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$? I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the ...
7
votes
2answers
119 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 ...
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 ...
6
votes
0answers
79 views

What's the complexity of solving a packing LP?

Linear Programming is in polynomial time weakly (when numbers are encoded in unary). AFAIK it remains open if it is possible to solve LP in polynomial time strongly (when numbers are encoded in ...
2
votes
1answer
99 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
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
1answer
39 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 ...
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?
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 ...
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
1answer
196 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 ...
1
vote
0answers
89 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$ ...
2
votes
1answer
99 views

How can k-means be reduced to Integer Programming

The k-means algorithm reduces to computing the objective function: $ \underset{\textbf{S}}{\operatorname{argmax}} \sum_{i=1}^k \sum_{\textbf{x}_j\in\textbf{S}_i} \lVert \textbf{x}_j - \mathbf{\mu}_i ...
3
votes
1answer
1k views

Help reducing 3-SAT to 3-COLORING

I am working on showing that 3-colorability is NP-complete. I read a few articles and walkthroughs on this but none are really clicking. I get to this part "Then for every variable xi that appears ...
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 ...
0
votes
0answers
38 views

Relation between Parameterized complexity and Approximation Algorithms

I want to know whether there is a relation between parameterized algorithms and approximation algorithms. Like there will exist a fpt problem for problem P iff it have some f-approx algorithm. I ...
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 ...