Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
0
votes
0answers
2 views

Subset sum to 0/1 knapsack

Show how an arbitrary instance (S, t) of Subset Sum can be translated into (i.e. reduced to) an instance of 0-1 Knapsack. Clearly indicate how the profits, weights, and capacity are determined. Hint: ...
0
votes
0answers
33 views

Restriction: polynomial time decision of instance is why needed to “decision Problem”?

I am reading book "combinatorial optimization 3rd edition(Bernhard Korte、 Jens Vygen)". (latest version is sixth.) There are some discriptions in this book that I don't understand Not all binary ...
4
votes
1answer
505 views

Assuming P != NP, what is the cardinality of the set of NP-Hard languages?

If P=NP, then every non-trivial language is NP-Hard, so clearly there are uncountably many NP-Hard languages. However it's less clear to me what the cardinality of this set is assuming P != NP.
0
votes
0answers
26 views

Unlimited size proof in PCP versus limited size

I have the exact same question as this guy, except I don't agree with the "verified" answer. Since in his answer the one to one mapping he describes depends on the input it makes the verifier $V'$ not ...
1
vote
1answer
512 views

How to prove graph isomorphism is NP?

I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.
1
vote
1answer
105 views

How do I reduce subset sum to another problem in NP?

I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following. Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it ...
0
votes
1answer
16 views

What does the search problem imply about the decision problem?

Let $\Pi_{dec}$ be an NP-complete decision problem and let $\Pi_{opt}$ be its corresponding optimization problem. Assume $\Pi_{opt}$ can be solved in polynomial time. What does this imply for $\Pi_{...
1
vote
1answer
34 views

Hamiltonian cycle, verifying and finding

If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle? My attempt is to delete an edge ...
2
votes
0answers
22 views

Bounds on tape alphabet size of a Turing Machine encoding

What is the max possible ratio between the tape alphabet size and the total encoding size in an asymptotic sense? Say if I take some TM and add more and more symbols to its tape alphabet, will the ...
-1
votes
0answers
16 views

I want to create an unsigned 8-bit adder/substractor and implement it in a logic circuit [closed]

I am having a hard time trying to implement an adder for 8-bits unsigned numbers with 1's complement but without using VHDL since I am new to this kind of stuff. But I know that I should use 8 full ...
1
vote
0answers
22 views

Does proving P^NP = NP have an implication in the P=NP question?

For language $O$, by $P^O$ I am referring to the set containing every language that can be decided by a polynomial-time deterministic TM with oracle access to $O$ (see Arora and Barak, Chapter 3, ...
3
votes
1answer
17 views

CNF satisfiability with a bound on number of clauses

Consider the CNF-sat problem with n literals and k clauses. If k scales linearly in n, we get np-completeness (e.g., 3-sat where each literal appears at most 4 times). Do we still get np-completeness ...
0
votes
0answers
7 views

why is the NL solution PATH negated unsufficient to prove unreachability

I'm currently reading into complexity classes and one think will not fit into my head. We are investigating NLogSpace with the Path/reachability problem. There is a nondeterministic LogSpace algorithm ...
0
votes
1answer
71 views

How to prove Exact cover problem is NP Complete using Vertex Cover problem?

Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from ...
1
vote
1answer
53 views

Is SEMIPRIME in P?

The title says it all: is there a deterministic polynomial time algorithm that tests for semiprimality? (A number $N$ is a semiprime if it is the product of two primes.) I don't understand the ''...
0
votes
0answers
18 views

Generating Turing machine with head over same cell [closed]

For given non-deterministic Turing machine $M$ we need to show how to create non-deterministic Turing machine $N$, such that $N$ recognizes the same language as $M$, works at most polynomially slower ...
5
votes
0answers
39 views

Analogue of the topology-computability correspondence for computational complexity

There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with ...
0
votes
0answers
46 views

Is there an O(n) solution for this problem?

I have found this problem on CodeForces.The problem is in the following link: https://codeforces.com/problemset/problem/729/C Problem Starts here: Vasya is currently at a car rental service, and he ...
0
votes
2answers
33 views

Can algorithms of arbitrarily worse complexity be systematically created?

We’ve all seen this: Can we get worse? Part 1: Can mathematical operations of increasing orders of growth be generated, with or without Knuth’s up-arrow notation? Part 2: If they can, can ...
3
votes
1answer
42 views

Given a set, partition it into ordered triples

I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$. The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$? I was trying to ...
2
votes
0answers
9 views

Derandomizing RG(1)

$RG(1)$ is the set of one-turn quantum refereed games. A definition can be found here: The class of problems for which there exists a BPP machine M such that, on input x: If the answer is '...
0
votes
0answers
32 views

Why does such reductions work [duplicate]

In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS) $V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$ The ...
0
votes
1answer
62 views

How to prove NP-completeness of this variant of the set cover problem?

The problem exactly: Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least ...
2
votes
0answers
19 views

What does it mean this relation: $BQP^{BQP} = BQP$

I am reading this paper by Fortnow, titled: One Complexity Theorist's View of Quantum Computing. In section 4, he states the following: Bernstein and Vazirani [BV97] show that BQP can simulate any ...
3
votes
1answer
35 views

Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
5
votes
2answers
545 views

Are there any proofs of exponential lower bound time complexity

I'm trying to understand what are the techniques to prove an exponential time lower bound. For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ...
5
votes
1answer
95 views

Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to ...
2
votes
1answer
62 views

Oracle separation P and BPP

I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in ...
2
votes
1answer
34 views

Interactive proof system for graph nonisomorphism

$\mathit{GNI} \in \mathrm{PCP}(\mathit{poly}(n),1)$ GNI is the language of nonisomorphic graphs. Given two grapsh $G_0$ and $G_1$ with $n$ vertices, a verifier expects $\pi$ to contain, for each ...
0
votes
1answer
96 views

Is this statement of P = NP in Agda correct?

Looking for a self-contained statement of P = NP in type theory, I stumbled upon this short Agda formalization (a cleaned up version is reproduced below). The statement here does seem to express the ...
1
vote
1answer
22 views

The space complexity of a function that allocates space based on the input value and not size

What is the space complexity of the following hyphotetical function: void function(int n) { int[] array = new int[n]; // allocate array of size n return; } ...
1
vote
1answer
25 views

Reductions from non decision problems

I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min ...
0
votes
2answers
34 views

Decide whether an $n$-bit positive integer is composite

Question: Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP? I know that for every composite number, a factor of the number is a ...
2
votes
1answer
56 views

Partition into pairs with minimum absolute difference, NP-hard?

I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t_1,t_2,\ldots,t_m$ where each $t_i\leq1$ for all $i$. The question is: can you select $m$ disjoint pairs $(a_i,b_i)$ from ...
6
votes
1answer
65 views

Is 3-colouring NP-hard for 5-colourable graphs?

Recently it was shown that it is NP-hard to find a 5-colouring of a 3-colourable graph. More generally, it is NP-hard to distinguish $k$-colourable graphs from those that are not $(2k-1)$-colourable, ...
2
votes
1answer
82 views

Can we solve this problem more efficiently than trying all possible combinations

Here is the context of the problem I am struggling with. I have a set of strings, for example: ...
1
vote
0answers
34 views

Time Complexity of Subset Problem

The Subset Exercise taken from LeetCode: ...
0
votes
0answers
24 views

Cook Levin Theorem (Sipser Proof) (phi move)

In Sipser's proof of the cook levin Theorem the move function (phi move) checks whether a given window is legal. For that we must have an exhaustive set of all possible legal windows to verify that a ...
1
vote
0answers
42 views

Find minimum pair number based on selection algorithm

If we have n balls in a red box (each ball is assigned a different number from 1 to n) and n balls in a green box (again each ball is assigned a different number from 1 to n). Lets say we have a ...
0
votes
1answer
20 views

Oblivious Machines and Input Dependency

So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input ...
-2
votes
2answers
73 views

Show that: $0.01n \log n - 2000n+6 = O(n \log n)$

Show that $0.01n \log n - 2000n+6 = O(n \log n)$. Starting from the definition: $O(g(n))=\{f:\mathbb{N}^* \to \mathbb{R}^*_{+} | \exists c \in \mathbb{R}^*_{+}, n_0\in\mathbb{N}^* s. t. f(n) \leq cg(...
1
vote
0answers
41 views

Reduce duplicate subset sum problem to distinct subset sum problem?

In duplicate subset sum problem (DuSSP), we are given a multiset $\{a_1,a_2,\ldots,a_n\}$ where some of the $a_i$ are duplicates. We can assume that $a_1\leq a_2\leq \cdots\leq a_m.$ We are also given ...
-2
votes
1answer
65 views

If A is polynomial time reducible to B and B is in NP, then A is in NP

If $A\leq_p B$ and $B$ is in $NP$, is it true that $A$ is in $NP$? What about : "if $A\leq_p B$ and $B$ is in $coNP$, then $A$ is in $coNP$"? Thanks in advance. I think both hold. If $B$ is in $NP$...
0
votes
0answers
17 views

First attempt at convert Context-Free Grammar into Chomsky Normal Form

This is my first attempt at converting a context free grammar into chomsky normal form. I think I have the correct answer, would just appreciate any feedback if I have gone wrong somewhere. Context ...
5
votes
1answer
80 views

Is GAP NP-hard with at most two balls per bins?

The generalized assignment problem (GAP) [1] is given by: Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and ...
0
votes
0answers
22 views

What is the complexity class of performing a perfect disassembly of binary code?

I have heard that the complexity class of performing a perfect disassembly of binary is undecidable. Is this correct? Are there any proofs of this?
1
vote
0answers
14 views

What are the requirements for a superset of P to be closed under karp reductions?

So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight ...
0
votes
0answers
72 views

Is “Extended Church-Turing Thesis” the same as “Cobham-Edmonds Thesis”?

I have been looking for any reference regarding the term: "Extended Church-Turing Thesis" [some people will call it, Strong Church–Turing Thesis]? Does anyone defined it or it is just people in ...
3
votes
0answers
20 views

Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...
0
votes
0answers
33 views

MaxClique is DP-hard

I want to show that MAX−CLIQUE={(G,k)|the largest clique of G is of size exactly k} is DP-complete The idea is reduce MAX-CLIQUE to C={(G1,k1,G2,k2) | G1 has a k1-clique and G2 does not ...