Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
3,745
questions
1
vote
0answers
9 views
Proof that $(L_{all})^C$ is not recursively enumerable
The problem:
We have the language $L_{all} = \{\operatorname{Kod}(M) | M \text{ is a turing machine and } L(M) = \Sigma ^*\}$
Hence, $L_{all}$ is the set of all encoded Turing machines (the $\...
1
vote
1answer
31 views
Algorithm for idempotent algebra
A boolean algebra expression can be converted into an idempotent algebra using
$$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$
where $\otimes$ is the ...
2
votes
1answer
76 views
How to prove LastToken problem is NP-complete
Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...
-1
votes
1answer
22 views
Another Subset sum problem
Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
-2
votes
1answer
31 views
How to find an solution set of subset sum when given an oracle to subset sum problem [closed]
The Subset Sum Problem: Input: a finite subset S of integers, and an integer t. Question:
does there exist a subset A ⊆ S such that the members of A sum to t? Suppose you have access
to an oracle that ...
1
vote
1answer
41 views
Proving NP-Complete problem by reduction of subset-sum
My assignment question as "given a multiset of symbols (letters) L from an alphabet Σ (thus, the same letter may appear in L multiple times), and a set of words W ⊆ Σ' , UseAllLetters asks if it is ...
1
vote
1answer
23 views
Subset sum to 0/1 knapsack
How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
2
votes
1answer
41 views
Finding a vertex coverage that is also an independent set
Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?
0
votes
0answers
34 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 ...
5
votes
1answer
512 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
520 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
107 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
17 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
72 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 ''...
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
48 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
36 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
63 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
23 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
66 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
35 views
0
votes
0answers
25 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
43 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
67 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 ...
