Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

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

Proof: Quick Sort Is $O(n*logn)$

I was given the follow proof: $$T(n)=n+2T(\frac{n}{2})$$ Will prove that $$T(n)=O(n*logn)$$ For $2:$ $$T(2)=2+2T(1)=2\leq 2*log(2)$$ Assume it is correct for $n-1$ in particular for $\frac{n}{2}$ ...
-1
votes
0answers
11 views

Complexity - Printing Permutations

On my course I was presented with the following definitions: Deterministic Machine - a machine that has one "route" for all inputs Non Deterministic Machine - a machine that has many "routes" for ...
2
votes
2answers
353 views

Show that UPrime = {1^n : n ∈ N is prime} is in P

I have this question to solve. According to my understanding, it basically requires a turing machine that outputs lines on the tape, with the number of the lines being any prime number. My idea is ...
0
votes
0answers
24 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
28 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
41 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
70 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
12 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
57 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
38 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
54 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
98 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
14 views

could anyone help me how to calculate the primitive operation for the matlab code involving bell number? [closed]

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
34 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
46 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
21 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
131 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
273 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
23 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
34 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?