# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,709 questions
Filter by
Sorted by
Tagged with
37 views

### Can this special case of Set Cover problem be solved in polynomial time?

Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s$ is a ...
20 views

### Reducing one problem to another

I know this is sort of a basic question, but I don't completely understand the following. Let $A$ and $B$ be two problems. If I take one instance $a$ of $A$ and one instance $b$ of $B$, and show the ...
53 views

### Complexity of still life extentions in Game of Life

The game of life is one of the most famous cellular automata in 2D. It has a variety of objects, some of them are moving like gliders, some have an oscillating behavior and others do not change at all,...
18 views

### Strategy to reduce between decision problems

I'm very new to complexity theory, please help me fill in the gaps in whatever knowledge I have acquired till now. A decision problem is a problem $X(D)$ that outputs for each input instance $I$, a ...
20 views

### Independent set problem with given black box

I'm very new to P and NP complexity classes and reductions. I'm trying to solve this problem and I want to verify my solution and if it is wrong, understand why. Suppose that I'm given a polynomial ...
35 views

### From binary to unary and EXPTIME

I read in [Razborov, "An equivalence between...", p.248] that It is well recognized in Theoretical Computer Science that when we change the representation of integers from binary to unary, ...
7 views

### Is there complexity hierarchy of worlds/environments that are used for simulation or reinforcement learning in AI?

Is there complexity hierarchy of worlds/environments (i.e. state space * action space) that are used for simulation or reinforcement learning in AI? Hierarchy like ...
24 views

### FO-Logic: Two theories in the same complexity class can always be reduced to each other in polynomial space and time

I am currently studying CS and came across a question in my lecture. Question: Two theories in the same complexity class can always be reduced to each other in polynomial space and time. This is part ...
68 views

### How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...
21 views

### Maximal edge weight clique of given size

Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. ...
203 views

### How it's possible decide CNF by having a turing machine that decide SAT?

Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
17 views

### Understanding P, NP with an example decision problem

I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...
27 views

### Need the time complexity of this conditional statement method

My idea of the program is : Input = n sets objective function ObjFn equals to O(n^3) Output = the order of n sets Steps: Applying ObjFn to all n sets Choose the n of the Minimum ObjFn to be ordered ...
20 views

### Calculate complexity of game of life(cellular automata) [duplicate]

I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells ...
33 views

### Reduction techniques in complexity

I am learning computational complexity and parameter complexity. In order to proof that a problem is np-hard, we should reduction one which is np-hard to the problem. However, I don't have any idea ...
28 views

### Proving correctness of Polynomial reduction

Given a problem A is NP-Hard and A ≤𝑝 B, is there a way to prove that B is also NP-Hard?
19 views

### Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

In a lot of the online explanation of complexity theory, the author proposes the following. "The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of ...
36 views

### Prove $\text{CorrectSuccintSolver} \in \mathbf{coNP}$

Define the following languages:  \text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in }...
53 views

### Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?

This question is directed at DFAs/NFAs and regular languages and regular grammars. Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
3k views

### Data structure for fast insertion and fast random element removal

I'm looking for a data structure that supports the following operations: add(elem) - Add an element to the data structure. remove_random() - Remove and return a random element. The best I got so far ...
39 views

### A different way of reducing subset sum to partition

For brevity, let $s(D) = \sum_{d\in D} d$ denote the sum of the elements in $D$. Given a set $A = \{a_1, \dots, a_n\}$ of positive integers, and a target value $K$, the subset sum problem is to ...
25 views

### Is Knapsack-optimization problem NP-hard while Knapsack-search problem NP-complete?

I am learning Computational Complexity. Is Knapsack-optimization problem (find an arrangement to maximize the value) known to be NP-hard, while Knapsack-search problem (find an arrangement so that ...
36 views

### Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular [duplicate]

I have a computer science question: Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular These are all the facts I have been able to gather ...
77 views

### Prove finding a spanning tree with no more than 50 leaves is NP-hard

This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard? I think it is and I'm trying to ...
41 views

### How do I use the definition of the "Big-Oh" notation to prove the following statements? [closed]

I need help figuring out how to prove the following statement using the definition of "Big-Oh" notation which says that ...
28 views

### What is the difference between NP hard and NP complete?

What is the definition of P, NP, NP-complete and NP-hard? here is a good answer but it really doesn't answer mym question. np-hard-: a problem A is NP hard if for all B$\in$NP, B is polynomial time ...
27 views

### Adversary argument and proving a lower bound of an algorithm. How does it work?

I need to understand how adversary argument works to prove the lower bound of an algorithm. For now, I am looking to prove that a "certain" algorithm that takes in input array requires omega(...
47 views

### Are there any FNP-complete problems with a unique solution?

Are there any FNP-complete problems where there's only one possible solution? For example, the travelling salesman problem can have multiple routes all shorter than $X$. There's only one shortest ...
44 views

41 views

Consider the following pseudo-code: counter = 0 for (k = 16; k > 0; k /= 2) for (j = 0; j < k; j++) counter++ I get that the time complexity is $... 1answer 14 views ### A query regarding the paper/statement: P=BPP unless E has sub-exponential circuits I was going thorough this paper: (P=BPP unless E has sub-exponential circuits: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf) and I am somewhat struggling with some basics from the ... 1answer 62 views ### Complexity difference of Vertex cover and Vertex coloring regarding parametrized algorithms I stumbled upon some problem in my understanding of the complexity classes FPT and XP. According to Wikipedia (and the Book "Parameterized Algorithms") we know the following about the Vertex ... 0answers 17 views ### Books to read after Computational Complexity: A Modern Approach? To be honest, I have not yet read this book, but it's fun to plan ahead. If I am able to read through the entirety of this book and solve all the problems, are there books to dive deeper into the ... 1answer 53 views ### If a TM accepts a non-regular language, its space complexity is$\Omega(\log \log n)$I have been given an assignment that I'm having a very hard time understanding. The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is$\Omega(\log \log n)$(... 1answer 67 views ### Design an optimal algorithm that finds 2 array indices in a sorted array such that$A [i] + A [j] = k$Text: ... 0answers 27 views ### Is there a link between the "padding argument" and the "padding lemma"? In computability theory here is what the padding lemma says : Every partial recursive function$\phi_x$has$\beth_0$indices and for each$x$we can find effectively an infinite set$C_x$of indices ... 1answer 60 views ### Is Max 3-SAT W-hard? Is Max 3-SAT a W hard problem, parmeterized by some parmeterize? I can't find the relevant literature. 0answers 32 views ### Regarding the definitions of time-constructible functions on Wikipedia I am reading the Wikipedia article on time-constructible functions and got confused by its definitions, given as follows: There are two different definitions of a time-constructible function. In the ... 1answer 22 views ### A query regarding Complexity class BPP and NP It is known that:$\Sigma_2^P \subseteq \Delta_3^P$i.e.$NP^{NP} \subseteq \Delta_3^P$.$BPP^{NP} \subseteq \Delta_3^P$If$\Sigma_2^P = PSPACE => BPP^{NP} \subseteq NP^{NP}$Doesn't that imply: ... 1answer 53 views ### Prove by induction$T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$Text of the problem: Solve the following recurrence equation and prove it by applying the principle of induction:$T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \...
Define the subset sum with interval integer target problem (SSIITP) as follows: SSIITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$. An integer $T$. SSIITP Output: True, if ...