Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
3,928
questions
1
vote
1answer
10 views
What does Bellantoni-Cook say about Cook-Reckov?
In implicit complexity theory they construct natural programming languages that are complete for various complexity classes.
An example, while there are many others, is Bellantoni-Cook where they ...
3
votes
1answer
57 views
Dynamic Program to solve an NP-complete partitioning problem
I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!
Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{...
1
vote
0answers
29 views
Detected if an undirected graph G has a cycle
Trying to understand complexity well, I found myself with the following problem.
Consider the following algorithm to detect if an undirected graph $G = (V, E)$ has a cycle.
Imagine that $V = \{1 ...|...
2
votes
1answer
24 views
Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?
Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following:...
0
votes
0answers
30 views
Validity of a simple polynomial-time reduction [duplicate]
Let say that P is an NP-hard optimization problem and Q is a problem with unknown complexity. Additionally, we have an algorithm for solving problem Q. We can solve problem P with input x in the ...
1
vote
1answer
27 views
Does this problem map to the Set Packing problem?
Let $G(m,n)$ be A bipartite graph $G$ with paritions $m$ and $n$ with the property that partition $\mathit n$ has two types of nodes (type1 or type2).
Given $G(m,n)$ and $k \in \mathbb Z+$:
Does $\...
1
vote
2answers
61 views
Proving NP-completeness of a surveilled graph problem
So suppose I have a graph consisting of a tuple $(V,E,A,g)$ where $V$ denotes vertices, $E$ denotes edges, $A$ denotes a subset of $V$ (i.e. $A \subseteq V$), and $g:A\rightarrow\mathbb{N}$ is a ...
0
votes
0answers
24 views
Is it decidable to know the number of positions used by a Turing machine for a fixed input?
I'm having trouble proving if the following language is recursive, recursively enumerable, or not r.e. at all: the set of all encodings of Turing machines $M$ such that the number of positions in the ...
-2
votes
0answers
13 views
Equation for optimization problem in linear programming
Suppose that you are trying to solve the optimization problem:
Maximize vā
x subject to Ax ā„ b for some AāR^(mĆn) (i.e. trying to solve an optimization problem in n variables with m linear inequality ...
0
votes
1answer
25 views
A non-polynomial reduction
Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say ...
2
votes
2answers
61 views
Complexity of $O(\log(n^n))$ vs $O(\log(n!))$
Is $O(\log(n^n)) < O(\log(n!))$? Is there any good/practical algorithm with this kind of complexity?
And also, to check my understanding of algorithmic complexity, are these two $> O(n\log(n))$...
-1
votes
0answers
11 views
1
vote
0answers
22 views
A pda that accepts all strings over an alphabet
If you were asked to construct a pda that recognizes all strings over the alphabet {a,b,c,d}, that is
L={w | w belongs to (a,b,c,d)*}
How would that be constructed? My idea is to have one state as ...
0
votes
0answers
28 views
Asymptotics of reccurence relation
I need to tell whether $\quad\exists a \quad T(n) = \omega(n^2)$
$T(n) = T(\frac{n}{2}) + aT(\frac{n}{4}) + n^2\\\\
\forall n<10 \quad T(n) = 1$
And if there is such $a$ I need to find the ...
0
votes
0answers
35 views
Isn't every polynomial time problem an NP problem?
See here. Knapsack problem -- NP-complete despite dynamic programming solution?
The only reason Knapsack problem is NP-complete is because input comes as binary numbers so n is actually 2^n. Since ...
1
vote
0answers
19 views
How does a PDA compare two configurations of accepting histories?
In Michael Sipser's book, they prove that ALL_CFG is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of implementation) a PDA goes on to compare ...
1
vote
0answers
10 views
Boolean circuit multigraph
Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer].
He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some ...
0
votes
1answer
24 views
If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?
Deciding bipartite hypergraph coloring is NP-hard:
While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-...
0
votes
0answers
36 views
Prove/disprove: $\frac{O(f(n))}{O(g(n))} = \frac{\Omega(f(n))}{\Omega(g(n))}$ [closed]
Prove/disprove:
$$
\frac{O(f(n))}{O(g(n))} = \frac{\Omega(f(n))}{\Omega(g(n))}
$$
While the definition of:
$$
\frac{O(f(n))}{O(g(n))}
$$
is:
$$
\left\{t(n) = \frac{x(n)}{y(n)} \colon x(n) \in O(f(...
0
votes
0answers
12 views
Why some website I cannot open? [closed]
I try to open many time this site this link: https://uopeople.influitive.com/users/sign_in however something wrong. This is what it says, This page isnāt workingambassadors.uopeople.edu redirected you ...
1
vote
1answer
21 views
Complexity of ODD-SMALLER-SAT
While familiarizing myself with polynomial hierarchy, I used this book which is written by Ingo Wegener. Now I'm practicing, and on page 132 I met this exercise:
Let us consider a Boolean formula $\...
-1
votes
0answers
9 views
Manipulating Arrays in Java [closed]
I have a program in which I have read a csv file and stored it in an array. My CSV file is made up of three columns of which two are integers and one is string. I want to create two parallel arrays ...
0
votes
0answers
22 views
how to write a language for context-free grammar generates the empty string?
How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ć}?
-2
votes
0answers
16 views
I want to know the complexity of this following code [closed]
include
include
include
void main()
{
char p[10][5],temp[5];
int i,j,pt[10],wt[10],totwt=0,pr[10],temp1,n;
float avgwt;
printf("Enter no of girls:");
scanf("%d",&n);
for(i=0;ipr[j])
{
temp1=pr[...
1
vote
1answer
38 views
Why is this function computable in polynomial time?
Given alphabet $\{0,1\}$, I read that the following function $f$ is computable in polynomial time relative to input $w$
$$
f(w) = w10^{|w|^2-|w|-1}
$$
i.e. $f$ can be a $TM$ that receives $w$ and ...
0
votes
0answers
20 views
Minimum pair-wise XOR of elements from two sets
I have two sets, $A$ and $B$, which both contain a large amount of hashed values.
What is the most efficient way of computing:
$$\min_{i,j} A_i \otimes B_j$$
2
votes
0answers
35 views
Are minimum boolean circuit sizes for small problem sizes of an NP-complete problem known?
I think that a table with the following numeric values would be very interesting, but I could not find any table online displaying them:
Choose any NP-complete problem (say, clique, but a problem ...
-1
votes
0answers
22 views
Logspace reduction from PATH to 2SAT
It is known that PATH (given a directed graph G and two vertices s,t is there a path in G from s to t), and 2SAT are NL-complete problems. Find a logspace reduction from PATH to 2SAT.
1
vote
0answers
17 views
Is there a recursive problem encoding the Turing completeness of a model of computation?
Suppose we have a model of computation $C$ we want to show to be Turing complete. The usual strategy would be to emulate within $C$ any model of computation we already know to be Turing complete (e.g. ...
10
votes
1answer
2k views
+50
What is wrong with this simple proof of P=NP?
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiabilty problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
1
vote
1answer
16 views
Consequences of the Time Hierarchy Theorem
The form of the Time Hierarchy Theorem that I have is this:
If $f$ is time constructible then $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(f(2n+1)^3)$.
We want the consequences of this to be that $\...
2
votes
1answer
82 views
$k$-coloring in BPP, implies $k$-coloring in ZPP
Consider the next problem:
$k$-COL: Given a graph $G=(V,E)$, does it have a valid $k$-coloring?
I need to prove that if $k$-COL is in BPP, then it is also in ZPP. In other words, show that if there ...
1
vote
1answer
15 views
Proving undecidability of HALT_tm by reduction
Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ ...
3
votes
1answer
40 views
Is there a complexity class QPP?
The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach ...
2
votes
2answers
30 views
Does the word “efficient” usually refer to polynomial time or polylogarithmic time?
This question is strictly about terminology.
I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and ...
0
votes
1answer
37 views
Complexity class of an algorithm
What is the complexity class of an algorithm that runs in $n^{\mathcal{O}(\sqrt{n}log(n))}$ time?
As $n$ gets large $\sqrt{n}log(n)$ increases at a very slow rate. Does this mean that the algorithm ...
4
votes
1answer
74 views
Query: Given a graph, is edge x in an optimal TSP tour?
Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph.
It may be argued that ...
2
votes
0answers
18 views
Clarification on the definition of strongly NP-hard
I am seeing two definitions of strongly NP-hard that seem to be slightly different:
A problem is strongly NP-hard if a strongly NP-complete problem has a polynomial time reduction to it.
A problem is ...
1
vote
1answer
19 views
Question about Circuit-SAT NP-Complete Proof
I have two questions about the proof that Circuit-SAT is NP-Complete from here (just the first 1.5 pages):
https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture22.pdf
The THEOREM 1 ...
2
votes
1answer
38 views
How to prove the NP-completeness of MOD-PARTITION
MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \...
1
vote
1answer
32 views
Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable
I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma_1$ is Turing recognizable.
I'm not sure what's the general way to approach this, but I noticed $A_{TM}$ is in $\Sigma_1$ ...
4
votes
0answers
36 views
Why is finding square root of perfect square $O(M(n))$
I saw this question and its answer on Theoretical Computer Science stack exchange and I can't understand why the complexity of finding the root is the same as that of a multiplication. My thought was ...
0
votes
0answers
28 views
Amdahl's Law and efficient algorithms
Does the efficiency of algorithm leading to better performance of the system can be attributed to Amdahl's Law?
or
Is the Amdahl's law only applicable for the analysis of efficient hardwares and ...
1
vote
0answers
85 views
how did the authors of the AKS-Paper come up with the upper bound for r? and what does the multiplicative order have to do with anything?
I have been recently reading the paper "PRIMES is in P", but unfortunately a lot the steps were skipped, which led to confusion. My main problem is with the upper bound on r which was not explained at ...
-1
votes
0answers
25 views
Difference between NP Intermediate and NP Complete [duplicate]
Assuming P ā NP
How do you determine whether a problem belongs in NP Intermediate or NP Complete?
Why does integer factorization belong in NP Intermediate, but the knapsack problem belongs in NP ...
1
vote
1answer
56 views
Space complexity of Travelling Salesman Problem
I am having trouble coming up with the space complexity of the TSP algorithm.
https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
To me the space complexity for the brute force is the ...
2
votes
1answer
81 views
Computational complexity of counting symbols
Consider the counting function $\{x\}^* \rightarrow \mathbb N$ that counts the number of occurrences of the symbol $x$.
I am confused about the (asymptotic) complexity of computing this function, ...
2
votes
0answers
55 views
Calculating number of intersections of a horizontal line with line segments efficiently
I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$.
Now, I'm given $q$ queries in the form of $...
1
vote
1answer
17 views
Argument in proving that function is not polynomial time in bit length of input seems faulty
I am currently solving a question that asks which of the following functions can be calculated in polynomial time:
$$n!, \binom{n}{5}, \binom{2n}{n}, n^{\lfloor \lg n \rfloor}, \lfloor \sqrt{n} \...
1
vote
1answer
34 views
Oracle queryās required
The variables $a,b,c \in \{0,1\}$, thus $a^k, b^k, c^k \in \{0,1\}$
I want to pass a query to an oracle that returns the coefficients of each term $(1,a,b,c,ab,ac,bc,abc)$ in the expansion of ...
