Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
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)$ (...
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 ...

1
2 3 4 5
95