Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,408
questions
1
vote
1answer
23 views
A problem about asymptotic functions
Are there two function $f:N\rightarrow N$, and $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?
My idea: i think because of for any $f:N\rightarrow N$, and $g:...
1
vote
1answer
48 views
Polynomial time verification of Graph Isomorphism problem
Using guess and check method, for two given graphs with the same number of nodes, a NTM selects a permutation of the node set and then checks if the edges are preserved.
The nondeterministic selection ...
0
votes
0answers
18 views
Length of PCP Proofs
Suppose a language $L$ has a non-adaptive PCP verifier which uses at most $r(n)$ random coins, and queries at most $q(n)$ locations of the proof, on inputs of length $n$. How can we show that there is ...
1
vote
2answers
58 views
Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?
In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
1
vote
0answers
47 views
+50
Reduction between Parity-SAT and approximate counting
Consider two problems as defined here.
Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases:
The number of satisfying assignments for $f(...
0
votes
0answers
50 views
Need help with a very specific Greedy Algorithm. Are there fast solutions?
i need help for a specific problem i have at work.
You have N number of rows in an array, each with some distribution of Numbers that range from 0 to N.Given an array of size 1000:
Row 1 might look ...
1
vote
1answer
30 views
What is the “formula” for “any chipher can be deciphered by a quantum computer”?
There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others.
P=NP BPP=NP in simple words means "any cipher can be deciphered by a ...
1
vote
0answers
18 views
Is there a concept of probabilistic quantum computers?
Answering my question https://cstheory.stackexchange.com/q/48527/61557 Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above ...
-5
votes
0answers
136 views
Is this the solution to halting problem?
The halting problem claims that it's impossible to have a machine that will always be able to predict if machine will halt with a given input. However, it is proven impossible due to machine giving a ...
3
votes
1answer
53 views
Why do we use DAG rather than trees to represent search space of a search problem?
I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
2
votes
1answer
100 views
Efficient algorithm to compute the diameter of a convex set?
Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the ...
-3
votes
0answers
14 views
Homework help algorithms [duplicate]
The data in the table below has been collected by a teacher at the end of two unit assessments. Produce a subroutine for an algorithm that could be used to count the number of students who achieved a ...
-4
votes
0answers
31 views
Prove that $f(L)=L_{\Sigma^*}$
When:
$f(L)=\{f(x) | x\in L\}, L\in R$
$L_{\Sigma^*} = \{\langle M\rangle | L(M)=\Sigma^* \}\notin RE$
and
$\langle M_{\Sigma^*}\rangle$ is TM that accept straight away.
For:
$f(\langle M\rangle)=\...
1
vote
0answers
36 views
Strong NP-completeness of numerical perfect matching
This is a follow-up to post Perfect matching problem, where nir proved weak NP-completeness.
Suppose you are given two sets of integers $L$ and $M$ both having $N$ elements. We want to match each ...
1
vote
1answer
172 views
Is this clique algorithm in polynomial time correct or might it have another time complexity?
I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity ...
1
vote
1answer
19 views
How to express complexity of two functions considering it is the same in big O notation
I have two functions. a and b.
Both have linear complexity O(n).
...
0
votes
1answer
35 views
Vertex cover of minimal graph
I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ ...
-3
votes
1answer
28 views
How to simulate two counters using one (FIFO) queue?
How to simulate two counters using one (FIFO) queue? (In terms of algorithms, unary stack.)
1
vote
1answer
14 views
Can inputs in the decision tree model be computed?
The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still ...
1
vote
0answers
15 views
Measure divergence in Particle Swarm Optimization
I'd like to monitor divergence/diversity in my swarm during the particle swarm optimization algorithm to measure when the swarm search space is converging.
This would be used as one metric to be ...
0
votes
0answers
18 views
Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?
I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...
0
votes
1answer
25 views
If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?
If $x \in L$ only if $x \in A$ and $x \in B$, where A is an NP problem and B is a coNP problem, I cannot place $L \in NP$ or $L \in coNP$ without implying that NP = coNP right?
1
vote
1answer
74 views
Perfect matching problem
Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*...
1
vote
1answer
50 views
Polynomial kernelization for Set Splitting
In a set system $(U, F)$, $F\subseteq \mathcal{P}(U))$, we say that a function $f: U \to \{0, 1\}$ is a coloring of $(U, F)$. A set in $F$ is split by $f$ if $F$Ā receives both colors.
The Set ...
0
votes
0answers
56 views
How to implement a Turing Machine that calculates log base 2 of n where n is a natural number and output in a unary format? [duplicate]
How would you construct a Turing Machine that calculates log2(n)?
The process must take in an input such as 4 and output the result in a unary format such as a 11 (11 = 2 in unary)?
In the final ...
-2
votes
0answers
44 views
$\forall A\notin RE$ prove that $L_A =\{\langle M\rangle : |A\cap L(M)|\ge10 \}\notin RE $
My solution for this question is:
Reduction from $L_A$ to $A$, in the following way $f(x)=\langle M_x\rangle$
Emphasis: $\exists$ 10 different words $w_1 ,\dots,w_{10}\in A$, otherwise $A$ finite $\...
-1
votes
1answer
64 views
For every Non Deterministic polynomial Turing Machine $M$ exists $L(\overline{M})\in P \Leftrightarrow P=NP$
The $\Leftarrow$ direction is straightforward.
On the other hand for $\Rightarrow$ direction I have an idea of the prove but I don't sure about it.
For NTM, Non Deterministic Turing Machine, $M$, for ...
0
votes
1answer
23 views
Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$
When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa.
I'm thinking that this equal to $P=NP$, but I saw a solution (...
1
vote
0answers
22 views
Generating a fast permutation function over an integer range
Is there a way to generate a bijection over integers $F : [0..n) \rightarrow [0..n)$ that satisfies the properties:
$n$ is arbitrarily chosen and can be any positive integer
$F$ generates a ...
3
votes
0answers
36 views
Hardness of an instance of a problem independent of algorithms?
The paper āWhere the really hard problems areā (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
-1
votes
2answers
39 views
Context Sensitive Grammar for the language $\{a^nb^nc^n\mid nā„1\}$
I tried many grammars and so far I got this one:
\begin{align}
&S \to aXbZ \mid abc \\
&XZ \to Ybcc \\
&Xb \to bX \\
&bY \to Yb \\
&aY \to aa \mid aaX
\end{align}
Is my grammar ...
1
vote
1answer
33 views
A question about domains in Karp reductions
A basic question or request for clarification regarding Karp reducibility:
Let $\Sigma^*$ be the set of all finite strings of 0's and 1's. Call a subset of $\Sigma^*$ a language. Let $\Pi$ denote ...
1
vote
1answer
26 views
What are skew arithmetic circuits?
I am trying to understand the definition of skewed circuits in these slides which is given as follows:
A circuit is skew if in each product gate, at least one product has degree $\le 1$.
I think ...
1
vote
1answer
27 views
The concept of the creation of a trapdoor in NP-complete or NP-hard problems
I am reading the book An Introduction to Mathematical Cryptography. In its chapter 7, there is the following statement:
In real world scenarios, cryptosystems based on NP-hard or NP-complete problems ...
1
vote
1answer
29 views
Must an optimization problem with a greedy algorithm belong to P?
If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the ...
1
vote
0answers
80 views
Need for Functions to be Increasing in Non-deterministic Time Hierarchy Theorem
I was going over the proofs of the non-deterministic time hierarchy theorem (the one in Arora-Barak and the one by Fortnow and Santhanam). They are available here:
http://theory.cs.princeton.edu/...
1
vote
1answer
18 views
Circuits and Closure Under Reductions
Suppose that $A$ and $B$ are languages such that $A\leq_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$?
Using similar ideas like Cook-Levin (...
2
votes
2answers
91 views
Is there a Zero-Knowledge proof for SAT?
I know that SAT can be reduced to (3 vertex) Graph colouring, and there is a Zero-knowlegde protocol (ZKP) for graph colouring. However, I am interested in a ZKP that can be performed directly on a ...
1
vote
0answers
19 views
Time constructible function T in equivalence of Turing Machines
I'm reading Computational Complexity by Arora and Barak and I had a doubt regarding a statement made about the equivalence of Turing machines:
For every $f\colon \{0, 1\}^ā ā \{0, 1\}$ and time-...
0
votes
0answers
31 views
Is there any proof that says “For each problem in NP there is a randomized algorithm that solves that problem in expected polynomial time.”
Is it known that "For each problem in NP there is a randomized algorithm that solves it in polynomial time"? If not true then is there any proof of that. Or does it belongs to the unknown ...
0
votes
1answer
59 views
Minimum absolute value of subset sums of integer values
$f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$
How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$?
When $\...
1
vote
1answer
66 views
What happens to the running time of an $O(n \ln n)$ algorithm if you double $n$?
Problem:
Suppose the running time of a certain algorithm is $O(n \ln n)$. We happens to the running
time of the algorithm if $n$ doubles.
Answer:
Let $R_1$ be the running time of the algorithm when ...
1
vote
2answers
40 views
How to analyse the time complexity of an algorithm based on the input values in addition to input size
I saw a joke on twitter today that got me thinking on how to perform a time complexity analysis of this algorithm such as you can express that the worst case is dependent on the input value in ...
1
vote
1answer
34 views
Why every finite language is polynomial?
I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$
0
votes
0answers
28 views
Techniques to prove lower bounds on randomized algorithms
I am interested in proving lower bounds for AM-like languages. The usual techniques for lower bounds in non-probabilistic machines don't work for probabilistic machines.
Intuitively, when I think ...
42
votes
11answers
9k views
Can a computer determine whether a mathematical statement is true or not?
I was reading Introduction to the Theory of Computation by Michael Sipser and I found the following paragraph quite interesting:
During the first half of the twentieth century, mathematicians such as ...
9
votes
2answers
1k views
Theory behind regex implementations
In a 2007 article, Russ Cox (at presents, he leads the development of the Go programming language at Google) argues that regex engines in languages like Java, Perl, PHP, Python, Ruby are built on a ...
-4
votes
1answer
40 views
Proof of existence of $L\in R\setminus P$
I saw some proof but I didn't understood it, any simple one?
1
vote
1answer
28 views
$\overline{SAT}$ vs. $UNSAT$, Is it the same?
I know this question may look stupid, but still..
Is the meaning of both "have no satisfiable assignment"?
1
vote
1answer
18 views
Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time
So I have the following language:
C = {<G,w>|G is a CFG in Chomsky normal form and w has more than one parse tree in G}
How to prove that this language is in P (decidable in deterministic ...
