Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,630
questions
0
votes
0answers
12 views
Turing reductions vs many-to-one reductions
If $A ≤_T$ B, and B is decidable, then A is decidable, prove or disprove. I could disprove that If $A ≤_T$ B, and B is semi-decidable, then A is semi-decidable by a counter example. But, how to prove/...
0
votes
1answer
25 views
If $A\leq_P B$ and $B\in \text{NP}$, is $A\in \text{NP}$?
Let $A\leq_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq_P B$ and $B\in \text{P}$ then $A\in \text{P}$.
My question is, if $A\leq_P B$ and $B\in \...
2
votes
1answer
69 views
If P!=NP, does there exist infinite hierarchy of languages between P & NP?
This looks to me as some tweaking or generalization of Ladner's result on NP-I languages, can some help me in the right direction? or redirect me to some sources where this generalization is ...
0
votes
1answer
44 views
Does there exist a language O such that $NL^O= Dtime(n^{logn})^O$? How to proceed with the proof in either case?
I do have some intuition(although I would like to be corrected) regarding why $NL!=Dtime(n^{log n})$ as for some $L \in Dtime(n^{log n})$ it might be required for the TM deciding it to read inputs of ...
1
vote
0answers
38 views
Square of a directed graph $G=\left< V, E\right>$
I have this question from CLRS book please.
Question: The square of a directed graph $G=\left< V, E\right>$ is the graph $G=\left< V, E^2\right>$ such that $(u,w) \in E^2 $ iff for some ...
2
votes
1answer
77 views
What is the regular expression for the language, {w | w does not contain the substring 11}
{w | w does not contain the substring 11}
What I am thinking: $(0^* 1 0^* )^*$
Is anything wrong with my expression?
Thanks in advance for your help!
-1
votes
0answers
25 views
A Query regarding Polynomial hierarchy collapse to a finite level [closed]
Assuming a hypothetical scenario that complexity class $PSPACE$ is shown to belong to complexity class $NP^{coNP}$ the Polynomial Hirerchy Collapses to a finite level.
Query 1: Which level the above ...
1
vote
1answer
16 views
One-tape Turing machine for doubling words (strings)
I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape ...
1
vote
1answer
22 views
Finding maximum clique given, for each edge, union of all cliques containing it
For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U_{e}$ of the edges of all cliques that contain $e$.
Can we determine, in polynomial time, for a given edge $e_{0}\in E$, the size of ...
0
votes
0answers
15 views
Where does this Oracle Problem belong in the Polynomial Hierarchy?
Given a problem $E_0$ such that:
Any valid solution $S_0$ if there is any is of polynomial length.
Assuming we are able to guess the solution $S_0$, for it to be valid:
i. There are a fixed set of ...
0
votes
0answers
15 views
A successful search takes $\Theta(1 + \alpha)$ time on average when resolving collisions by chaining
I would to discuss a proof found in CLRS book please.
Theorem: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1 + \alpha)$, on the average, under ...
3
votes
0answers
60 views
3SAT to 1-in-3SAT reduction with additonal constraints [closed]
The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows:
For each 3SAT clause: $x+y+z=1$ Introduce 4 new variables ${a,b,c,d}$ and replace original clause with below 3 clauses:
$R(x−,a,...
-1
votes
0answers
43 views
single-tape Turing machine
I am reading an introductory text on Turing machines( https://en.wikipedia.org/wiki/Turing_machine) and I have some questions. The first one is the following:
Prove that there is a single-tape Turing ...
1
vote
0answers
22 views
NP-hardness proof of an optimization problem with real values and real input in the decision problem
Question - Let's suppose we have an optimization problem $\mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $\mathcal{P}_D$ (please see definitions ...
1
vote
0answers
27 views
Approximation classes for optimization problems with real values
Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.?
If my understanding is correct a ...
2
votes
0answers
61 views
NP-hardness proof of an optimization problem with real values and rational input in the decision problem
I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated.
For the question, take the ...
0
votes
1answer
35 views
How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?
The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
0
votes
0answers
15 views
Prove that if $k$ was the $(i+1)$st key to be inserted into the hash table, then $E[probes(k)]=\frac{1}{1-\frac{i}{m}}$
Theorem: Inserting an element into an open-address hash table with load factor α requires at
most $1/(1 − α)$ probes on average, assuming uniform hashing.
By following unsuccessful search strategy, we ...
1
vote
1answer
22 views
Number of probes in a unsuccessful search in open address hashing
Theorem: Given an open-address hash table with load factor $α = n/m < 1$, the expected number of probes in an unsuccessful search is at most $1/(1−α)$, assuming uniform
hashing.
Let us define the ...
1
vote
2answers
60 views
Disprove sorting in O(log(n))
Assume an array $X=[x_1,...,x_n]$ is given, where each $x\in X$ is an integer. Array $X$ is sorted if $x_1 \le ... \le x_n$. Typical sorting algorithms have a worst-case performance of $\mathcal{O}(n\...
0
votes
1answer
42 views
Simplifying the Language of this DFA
Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
1
vote
1answer
62 views
Another version of Geography Game
The classic definition of normal “Geography Game” is the following:
Each player on her turn choose a word such that starts with the last letter of the previously choosen word by another player. (...
2
votes
1answer
58 views
What is the computational complexity in big O notation of an algorithm computing n^n?
I have a number n of size s. What is the computational complexity in big O notation of an algorithm computing n^n? Let's assume I'm using exponentiation by squaring. The result size doubles when we ...
1
vote
0answers
24 views
Is non-equivalence of regular expressions with union, concatenation and squaring NEXPTIME-hard?
On wikipedia, page about EXPSPACE it says
An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions ...
0
votes
0answers
14 views
Do time-constructible functions exist in relativized worlds?
I know that time-constructible functions are necessary to prove the Time Hierarchy Theorem and being computable functions they are computed by Turing Machines. I'm just confused in that since the Time ...
6
votes
0answers
121 views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
0
votes
0answers
23 views
Number partition subjected to the cardinality of subset
I hope someone can take some time to consider the following problem and welcome to discuss together.
Number partition problem is one of well-known NP-hard problems.
Now I am considering the hardness ...
2
votes
0answers
31 views
Under ETH: $\exists$ Problem unsolvable in $2^{o(n)}$ $\Leftrightarrow^?$ 3-SAT can be represented in linear bits
It is a popular open question if there is a problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH. I recommend reading that question first. That question states that, assuming the ETH ...
-2
votes
0answers
23 views
I have explored all the www on what the "computational methods" are, and I still have a doubt on what they really are?
after spending all this time surfing the www to find out what "computational methods" are, I concluded that they are the methods that allow us to solve complex problems using computers, ...
1
vote
1answer
39 views
Why is Independent Set "at least" and Vertex Cover "at most" k
The decision version of the Independent Set and Vertex Cover problems are phrased as:
Given a graph G and a number k, does G contain an independent set of size at least k?
Given a graph G and a ...
1
vote
1answer
76 views
Is $P=NP$ even if we need infinitely many algorithms?
If $P=NP$ was proven with an algorithm, would that have to mean that there is one algorithm that has to work for all inputs of length $n$?
More specifically, what if there were infinitely many ...
1
vote
2answers
39 views
Does $P=NP$ require an algorithm that uses polynomial space?
if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
0
votes
0answers
31 views
Prove that Horner's method produce only 6 collisions on 50000 English words
Polynomial for producing hash values:
$p(z)=a_0+a_1z+\cdots, a_{n-1}z^{n-1}$
Honor's method for that polynomial:
$$
p_0(z)=a_{n-1} \\
p_i(z)=a_{n-i-1}+zp_{i-1}(z), (i=1, \cdots, n-1)\\
$$
Problem: For ...
0
votes
0answers
28 views
What is the complexity of (prime?) factorization with a fixed number of primes?
I was wondering what the complexity of factorization (on quantum computers or classical computers) is if we know that there must be exactly two prime numbers and we know the two prime numbers.
For ...
1
vote
0answers
81 views
Horn formulas, existential second order logic and the Cardinality constraint
Consider this Problem $P$ as follows: $~$ Given a set $S$ and a constant $K$.. $~$Is there a subset $M$ of $S$, such that $|M| \ge K$?
Of course, $P$ can be easily solved in time polynomial in $|S|$.. ...
1
vote
0answers
36 views
What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?
For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
2
votes
1answer
28 views
Is ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$?
I'd like to know if ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$ or not.
I know ${\Sigma_2^\textsf{P}}^\textsf{NP}=\Sigma_3^\textsf{P}\subseteq\textsf{PH}$, and I wish to know if this ...
0
votes
2answers
31 views
What does FTP and XP stand for in "$FTP \subsetneq XP$? [duplicate]
What do FPT and XP stand for in this question? Proving FPT is strictly contained in XP
I don't have enough reputation to comment on that post and ask and I couldn't find the meanings of these ...
2
votes
1answer
130 views
Proving FPT is strictly contained in XP
In their book Fundamentals of Parameterized Complexity, Downey and Fellows claim (in chapter 27.1) that $\mathrm{FPT}\subsetneq \mathrm{XP}$, and that this is a "basic result" that follows ...
1
vote
1answer
21 views
Complexity of checking graph separation
Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
2
votes
1answer
14 views
Why is the communication complexity of f on disjunction of x and y is bounded above by 2D(f)
Let f be a Boolean function on n variables. Let $DC(g)$ and $D(g)$ denote the deterministic communication complexity and the decision tree complexity of $g$. Why is the following inequality true:
$$DC(...
0
votes
0answers
15 views
Is job shop scheduling J|pij=1|Cmax is still NP complete?
Is the job shop scheduling, where the processing time is 1 time-unit for all operations ($J|p_{ij}=1|C_{max}$), still NP complete or not?
Are there any literatures that have a proof?
3
votes
1answer
79 views
Is 3-UNSAT problem coNP-complete?
The 3-SAT problem, i.e. the problem whether a given Boolean formula consisting of clauses of at most 3 literals is known to be NP-complete. Then it’s complement, i.e. whether such a formula is ...
2
votes
1answer
54 views
How does fan-out change circuit complexity?
Edit: Here's maybe a clearer presentation of my question. In a Boolean formula, all the gates have fan-out 1, and the graph representing the formula is a tree. In a Boolean circuit, the gates can have ...
0
votes
0answers
23 views
Is there a reduction from 2sat to bpm?
Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
0
votes
0answers
48 views
is there a theory consider on infinitely many recursion?
of course there is a theory that how many recursive calling the same system to solve problems, this theory is "recursion theory", If i know correctly.
and recursion theory is computability ...
0
votes
1answer
62 views
What is the most efficient algorithm for calculating factorials? [duplicate]
Calculating the factorial n! by the algorithm that defines it is of O(n) complexity because it requires n-1 multiplications to find the solution. Is there an algorithm that is any faster than that?
2
votes
0answers
87 views
Why there is $\log n$ factor in time constructible definition?
I saw two different definitions of time constructible functions.
In Sipser (third edt), Definition 9.8, defines $t(n)$ is time constructible if $t(n)\geq O(n \log n)$ and maps $1^n$ to the binary ...
1
vote
1answer
67 views
What is the fastest classical "period-finding" algorithm that can replace the Quantum Fourier Transform in Shor's algorithm?
Shor's algorithm uses the Quantum Fourier Transform to find the period the function a^x mod N with "a" being a constant integer less than N and N being a ...
0
votes
2answers
57 views
Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k
I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G.
My algorithm is as follows:
Generate all subgraphs of size k, and check ...
