Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

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

1
2 3 4 5
89