# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

3,805 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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), ...
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 ...
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 ...
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 ...
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 ...
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= 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 ...
55 views

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 ...
39 views

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 ...
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 ...
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 ...
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?
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$ ...
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}$) ...