Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
3,805
questions
0
votes
0answers
20 views
Use the Rice's theorem to prove that the following property of a Recursive Enumerable language L is undecidable
This exercise was taken from the book "Languages and Machines: An Introduction to the Theory of Computation" by Thomas Sudkamp. It refers to exercise 12 (b) chapter 12. Given a language L which is ...
1
vote
1answer
16 views
Can someone explain me the Credit-Debit proof method for calculating operations?
I've started taking a data structure course and we are currently learning about different data structures. We also learned when to increase the capacity of an array by creating another array with ...
0
votes
0answers
12 views
longest sequence (of same digit) count with k changes allowed
Need to find the longest sequence count from the array, where it's allowed to change k elements.
i,e [1,1,3,4,3,3,10] and k=2 the answer should be 5, as k=2 means ...
1
vote
0answers
26 views
Spaced-bounded Probabilistic Turing Machine Always Halts
For example, in the definition of BPL, we require that the probabilistic Turing machine has to halt for every input and every randomness. What is the reason for us to define them this way? What would ...
0
votes
1answer
21 views
Dominating set in bounded degeneracy and bounded degree graphs
I believe Minimum Dominating Set (MDS) is NP-hard for bounded
degeneracy and their subset bounded degree graphs, but
a paper appear to suggest tractability.
Enumeration of Minimal Dominating Sets and ...
1
vote
1answer
52 views
An NP-hard problem reduces to its complement?
I found this statement in a true/false test section:
Could someone explain in laymans why this is a true statement?
My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
2
votes
1answer
40 views
Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?
Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)
polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
1
vote
2answers
68 views
Clique-problem for planar graph
I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion
This follows already from Kuratowski's theorem: a clique is at ...
0
votes
0answers
11 views
Learning algorithm analysis
Im learning order of algorithm
For x>=2, and rand(x) is function that return 1 value from 1 to x-1 which have uniform probability $\frac{1}{x-1 }$ And max(x,y) output bigger value and min(x,y) output ...
2
votes
0answers
54 views
Proving a pattern exist in a string without revealing where
Some time ago i read the following problem (i don't remember the article from which i read it from) :
"Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), ...
1
vote
1answer
37 views
Why not implement Union-Find structure using root as the direct parent?
I just learned about using UF with union by rank and path compression. A path can be compressed via attaching a node to its root after Find is called on the node. If the goal here is to flatten the ...
0
votes
1answer
35 views
In which paper is written that you can transform one problem to another to show NP-completeness?
For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard:
Post
I am searching for a scientific paper to cite where it is written, that ...
0
votes
0answers
36 views
Boruvka algorithm in Elog(log(V)) complexity
I am trying to implement Boruvka algorithm with the use of fibonacci heaps. My idea is the following:
Since Boruvka's algorithm operates like this:
Input is a connected, weighted and un-directed ...
3
votes
1answer
93 views
Compare two complexity functions having the same asymptotic complexity
For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found:
$A1: T_{A1}(n)=4n^2 +7log(n^2)$
$A2: T_{A2}(n) = 4T(n/2) + log(n)$
Say, technically ...
-3
votes
0answers
13 views
could anyone help me how to calculate the primitive operation for the matlab code involving bell number?
Could anyone help me to calculate the primitive operations for the following code:
n=[3]
for t=1:length(n)
b(1)=1
for i=2:n(t)+1
b(i)=0.0
for j=0:i-2
b(i)=b(i)+nchoosek(i-2,j)*b(j+1)
end
...
2
votes
1answer
55 views
Are problems in NP $\cap$ coNP less difficult than those in NP-complete?
I am taking a complexity class now, and I struggle to understand the concept of "hardness":
Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \...
0
votes
1answer
32 views
Calculating match % and ranking according to that
I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown ...
2
votes
1answer
46 views
PSPACE-completeness of DFA intersection problem
Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness.
It seems to me that I ...
0
votes
0answers
48 views
Algorithm Analysis - Binary Search Algorithm
The problem is from Data Structures and Algorithm Analysis Edition 3.2 (Java Version) Book from Clifford A. Shaffer. It is from the third chapter exercises, problem number 3.13.20.
Below is how it is ...
2
votes
0answers
24 views
On the hardness of constraint satisfaction
I am interested in the hardness of the following question.
Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\...
0
votes
0answers
28 views
Does mapping sorted input to unsorted output prove $P\ne NP$
Consider two sets of the same length that both contain every $n$-bit value. The first set is sorted, but the second set is unsorted and randomly arranged. Since both sets contain all possible $n$-bit ...
1
vote
1answer
39 views
Proof that $G$ is a yes-instance of IDS $\iff$ $f(G)$ is a yes-instance of SAT
Consider the Independent Dominating Set problem with a directed graph $G=(V,E)$ as instance and the properties that:
$\forall (u,v) \in E, \{u,v\}\nsubseteq S$
$\forall v \in V: v \in S \lor \exists (...
0
votes
1answer
28 views
how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$
how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then
${NP = P ? }$
1
vote
0answers
19 views
Blum complexity measure for lambda calculus
Is there a formal complexity measure for lambda expressions which satisfies the Blum axioms and measures the complexity of reducing the expression to its normal form?
I assume that the complexity ...
1
vote
1answer
10 views
P and polynomial sized circuits
What can we say about decision problems having a polynomial time algorithm, ie, in $P$? Do they always have polynomial sized circuits (but not circuits of polynomial depth)?
1
vote
0answers
19 views
Confusion about complementation of an NP language with oracle and coNP with oracle
Hello Stackexchangers,
I've come across a confusion in one of my exercises.
I was supposed to prove $\Pi_{n+1}^{p} = (\textit{co-NP})^{\Sigma_{n}^{p}}$, where the superscript operator in $M^{A}$ ...
0
votes
1answer
22 views
Partitioning a set based on binary predicate
Given a collection of objects $X = (x_0,x_1,...,x_{N-1})$ and a binary predicate $F$ which takes as parameters elements of the collection, find a better than $\mathcal{O}(N^2)$ algorithm which ...
1
vote
1answer
23 views
Size, depth, and time of circuits
Can polynomial depth circuits (with, let's say AND, OR, and NOT gates) be simulated in polynomial time?
1
vote
0answers
24 views
Looking for some references on voting theory
After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 ...
2
votes
1answer
44 views
Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)
I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time ...
4
votes
0answers
24 views
Strongly connected subgraph that contains no negative cycles
Is there an efficient algorithm that solves the following decision problem:
Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
0
votes
1answer
20 views
Clarifying what it means to be Strongly NP-Complete
Wikipedia defines strongly NP-Complete as:
A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the ...
4
votes
2answers
29 views
Complexity of list coloring $K_n$ with $n$ colors
The list coloring problem is, given a set $L(v)$ colors for each vertex $v \in G$, is there a proper vertex coloring, $c$, of $G$, such that $c(v) \in L(v), \forall v$.
I was wondering, for complete ...
-1
votes
0answers
27 views
Problems in logspace have polyomial size branching programs
Prove that if $A$ is a language in $\mathsf{L}$, a family of branching programs $B_1 , B_2 , \ldots$ exists wherein each $B_n$ accepts exactly the strings in $A$ of length $n$ and is bounded in size ...
9
votes
1answer
210 views
Subset sum problem for permutations
Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, ...
3
votes
2answers
125 views
Union of a language in P and a language in NP\P
TRUE or FALSE Statement:
Assume that $P \neq NP$. Then, for all languages $L_1$ and $L_2$, if $L_1$ is in P and $L_2$ is in NP but not in P then $L_1 \cup L_2$ is in NP but not in P.
I have a ...
2
votes
1answer
272 views
O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?
I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list:
Initialize an array of integers "colors" with V elements being 1
Using ...
-1
votes
0answers
22 views
What is the difference between super-polynomial time and exponential time?
What is the difference between super-polynomial time and exponential time?
Any differences?
1
vote
0answers
32 views
Complexity problem reduction?
Let say A and B are two decesion problems where A $\le$ B polinomial reduction is true.
Is this : A̅ $\le$ B̅ also true?
If so, can you show an exemple, if not why?
1
vote
1answer
38 views
Which combinatorial problem is similar to this problem?
I have $n$ clients and for each client I have different options to choose from, for example, $C= \{C_1,C_2 \}$. For each combination of $n$ options, there is a cost. I want to choose the best ...
2
votes
1answer
64 views
Is SAT a single language or a union of languages?
I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
0
votes
2answers
54 views
Why guess $\Theta(n^2)$ for the substitution method of worst-case partitioning
In the book
Introduction to Algorithms (3th edition) chapter 7
the recurrence of the running time of quicksorts partitioning is given by $$T(n) = T(n-1) + \Theta(n)$$
as the worst-case happens ...
1
vote
1answer
30 views
What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?
If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
3
votes
2answers
87 views
Coloring an interval graph with weights
I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of ...
4
votes
1answer
48 views
Partition into paths in a Directed Acyclic Graphs
I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths.
When $b_i=1$ for all the ...
0
votes
0answers
15 views
What does a model X need to be so that one program of $X/O(1)$ solve in $X$?
Let $X=P$, then we can have function
...
0
votes
0answers
21 views
What difference does PromiseUP make instead of UP in Valiant Vazirani? [closed]
Why does P=UP not imply PromiseP=PromiseUP which would give NP=RP from P=UP?
2
votes
1answer
53 views
Proof of $\mathsf{NP}^\mathsf{BPP} \subseteq \mathsf{BPP}^\mathsf{NP}$
How to show that $\mathbf{NP}^{BPP} \subseteq \mathbf{BPP}^{NP}$?
I tried to build $NTM$ $M_{NP1}$, which uses $PTM$ $M_{BPP1}$. Show that there will always be $PTM$ $M_{BPP2}$, which uses $L ($$NTM$ ...
1
vote
0answers
38 views
Is Dots and Boxes complementary to the game of Go?
I've read that La Pipopipette is known to be NP-hard. I have not yet found analysis specifying an exact complexity class for Dots and Boxes, or for some variations in the analysis of Go.
Here's a ...
0
votes
0answers
18 views
Proof that Special case of SUBSET SUM is in P [duplicate]
So i know that SUBSET SUM is in NP. But given the following special case:
The numbers $\ a_i,...,a_n $ with $\ i= 1,...,n-1 $ fulfill the condition: $\ a_i|a_{i+1} $ ($\ a_i $ divides $\ a_{i+1} $) ...
