Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,709
questions
0
votes
0answers
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 ...
1
vote
1answer
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 ...
5
votes
0answers
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,...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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, ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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. ...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
-2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-4
votes
1answer
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?
0
votes
0answers
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 ...
2
votes
1answer
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 }...
1
vote
0answers
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 ...
12
votes
3answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
-2
votes
1answer
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 ...
1
vote
0answers
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(...
0
votes
3answers
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 ...
0
votes
2answers
44 views
If $\Sigma_i^P = \Sigma_{i+1}^P$ then for all $k \ge i$ holds $\Sigma_k^P = \Sigma_{k+1}^P$
I am struggling with the following remark from lecture:
Suppose the Polynomial Hierarchy collapses at the $i$-th level, i.e. $\Sigma_i^P = \Sigma_{i+1}^P$. Then for all $k \ge i$ holds $\Sigma_k^P = \...
1
vote
0answers
21 views
What happens if we change $\mathcal{BQP}$ to allow quantum bits, but not quantum gates?
In the definition of the class $\mathcal{BQP}$ found in textbooks we (as the circuit builders) have access to an unlimited number of deterministic zero-initialized qubits and to a finite set of ...
1
vote
0answers
39 views
Simple example of LogSpace reduction
In general, how can I verify that my many-one reduction is a LogSpace reduction? E.g. I was looking at the proof of HORN-SAT is P-complete via logspace reduction.
It would be ok even if someone makes ...
6
votes
0answers
61 views
Computing tr(ABCD...)
Suppose we have $k$ $n\times n$ matrices $A,B,C,\ldots$. Is there a way to compute/approximate the trace of their product much faster than computing/approximating the full matrix product? IE, ...
2
votes
2answers
169 views
Why can't I use a polynomial-time reduction for proving P-completeness?
According to the Wikipedia page on P-complete,
a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate ...
0
votes
2answers
52 views
P vs NP Clarification
A problem is solvable in polynomial by a deterministic turing machine, and no solution exists which benefits from parallelism.
Will it be P or P-Complete or NP or NP-Complete?
0
votes
3answers
31 views
For 3CNF unsatisfiable boolean formulas, does it take exponential time to transform them into disjunctive form？
From the link Solving SAT by converting to disjunctive normal form, I learnt that the algorithm to transform any boolean formula to disjunctive form takes exponential time in worst case.
But I have a ...
0
votes
1answer
15 views
Polytime Mapping Reduction from Language A to Language A (identity)
How would I create a polytime mapping reduction to prove A ≤p A for any language A.
I was thinking to assume A is in P to start.
For every 𝑥: 𝑥∈𝐴 iff 𝑓(𝑥)∈𝐴.
But I am not sure what to do from ...
0
votes
1answer
23 views
NP-Completeness of SAT with given hamming weight k [duplicate]
I think that the following problem is NP-Complete but I don't have any idea of how doing the reduction.
Input: A propositional formula $\varphi$ and a number $k$.
Output: Yes if exists an valuation $\...
1
vote
1answer
41 views
Time Complexity Sigma Notation
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 $...
0
votes
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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)$ (...
1
vote
1answer
67 views
2
votes
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 ...
2
votes
1answer
60 views
Is Max 3-SAT W[1]-hard?
Is Max 3-SAT a W[1] hard problem, parmeterized by some parmeterize?
I can't find the relevant literature.
2
votes
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 ...
0
votes
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: ...
2
votes
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 \...
0
votes
1answer
34 views
Subset Sum With Interval Integer Target
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 ...
2
votes
2answers
28 views
Convert float array to lower or higher integer, find sum(integers) == round(sum(floats)), reducible to subset sum?
You have an array of floats, for example:
...
