Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
2
votes
0answers
88 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 ...
-1
votes
1answer
53 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
17 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
67 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
69 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
46 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
71 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
75 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
27 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
16 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
1answer
169 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
27 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
33 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 ...
1
vote
1answer
66 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
85 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
42 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
34 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
86 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
41 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
29 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
56 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
149 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
23 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
17 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
18 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
120 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
63 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
35 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
52 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
103 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
91 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
82 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
163 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 ...
0
votes
0answers
25 views

Polynomial time function vs polynomial time algorithm

In the book Proof Complexity By Jan Krajicek, the definition of a functional propositional proof system is given as: Definition 1: A functional propositional proof system is any polynomial time ...
1
vote
1answer
117 views

Why does IP = PSPACE

Can anyone give an intuitive explanation to why IP = PSPACE, or at least one direction of it? I looked at many research papers but its very hard to understand the formalism unless you have a solid ...
0
votes
0answers
20 views

Reduction from monotone 1 in 3 SAT to Planar monotone 1 in 3 SAT

It is known that both 'Monotone 1 in 3 SAT' and 'Planar Monotone 1 in 3 SAT' are NPComplete. Given a large 'Monotone 1 in 3 SAT' instance how can it be reduced to the planar version of the problem ...
1
vote
1answer
77 views

Complexity of LTL realizability of safety games with Next operator only

It is known that the computational complexity of deciding whether an LTL specification is realizable in a safety game is 2EXP-complete (that is, you receive an LTL formula, where some variables belong ...
0
votes
0answers
30 views

Logarithmic space and time computable function for sequences over $\{0,1\}$

Given $\sigma_1 \dots \sigma_n$ a sequence or word of length $n$ over $\{0,1\}$ I was wondering if there is a computable function to calculate $\sigma_m$ in $\log(P(n))$ time where $P(n)$ is some ...
1
vote
0answers
70 views

VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) ball)

What is the VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) balls)? A $k$-dimensional $l_1$ ball with radius $r\in \mathcal R$ and center $\mathbb v\in \mathcal R^k$ is $\{\...
1
vote
1answer
79 views

Details wanted on the reduction from Circuit Value to CFG Membership

Consider a Boolean Circuit $C$ which takes $n$ inputs and has one output. Notation: Let $\textit{size}(C)$ be the size of circuit $C$: the total number of gates in $C$. Let $G = (V,\Sigma,R,S)$ be a ...
0
votes
1answer
70 views

Tic-Tac-Toe in PSPACE

Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
-5
votes
1answer
67 views

Really confused

Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this? P = NP P ⊊ NP P ≠ NP NP ⊆ P
0
votes
0answers
35 views

A relaxation-free variant of Dijkstra's shortest path algorithm

I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
2
votes
1answer
32 views

Padding in proof of space hierarchy theorems

Referring to the Wikipedia proof : Wikipedia proves the space hierarchy theorem using the following language: $$ L = \{ (\langle M \rangle, 10^k) : \text{$M$ does not accept $(\langle M \rangle, 10^k)$...
1
vote
1answer
40 views

Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain

Determine if for given some $L$, $S_L=\{\ L(M) | <M>\in L \}$ then for any $L$, if $S_L=RE$ then $L\in R$. Correct or Incorrect and explain why. I think the claim is incorrect, and I'm trying ...
2
votes
1answer
71 views

Is there a difference between extremely slow growing functions and constants with respect to computable functions?

So let's say we have the function $f(n)$ that gives $k$ such that $k$ is the smallest number that gives a busy beaver function $B$ value from input $k$ that is greater than $n$. Or more succinctly the ...
1
vote
1answer
66 views

What does an NP reduction look like?

From my theory of computation lecture I recall: If $A \le_m B$ and $B$ is decidable then $A$ is decidable (uses a computable function as a reduction). If $A \le_p B$ and $B$ is in P then $A$ is in P ...
0
votes
0answers
42 views

Reduction from Edge-Coloring and Vertex-Coloring to a new problem

I have a question from a test I did and failed, a question I failed to do. In short: the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined. The new ...
-1
votes
1answer
79 views

Reduction from problem A to another problem B

I have a question from a test that I failed to pass, I failed to do the question. The question: Let A and B have two languages so that there is a reduction function f: $A\leq _pB$. Suppose that $A \in ...

1 2 3
4
5
95