Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

4
votes
1answer
108 views

Can we check in polynomial time if the language of a DFA is closed against Kleene star?

I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it.
1
vote
0answers
21 views

$\mathsf{PP}$ compared to $\mathsf{\#P}$

Since know that $\mathsf{TC^0\subsetneq PP}$, I wonder if we also know that $\mathsf{TC^0\subsetneq\#P}$? I understand that $\mathsf{\#P}$ is in counting hierarchy.
4
votes
0answers
50 views

Adleman's theorem to $\mathsf{P=BPP}$

Adleman's theorem gives $$\mathsf{BPP\subseteq P/Poly}.$$ Why is this theorem considered progenitor to derandomization conjecture that $\mathsf{P=BPP}$? Does it mean Adleman's result could be ...
0
votes
0answers
26 views

Is $AM = AM[2]$?

Any $k$ round AM can be reduced just two rounds whereby Arthus just does the $k$ coin tosses and passes on the information to Merlin. Merlin sees all the coin toss results and computes everything ...
0
votes
0answers
39 views

2-depth arithmetic circuits and VP vs VNP

the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary: is this new paper Sums of ...
0
votes
3answers
54 views

Need for random bits in final PCP theorem statement

PCP theorem states that $$PCP(O(\log n),O(1))=NP.$$ Could we not run through $O(\log n)$ bits deterministically? Does PCP theorem statement mean any set of $O(\log n)$ random bits out of $2^{O(\log ...
2
votes
0answers
34 views

Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $

I was reading the following paper by Jim Kadin, "$P^{NP[O(\text{log } n)]}$ and sparse Turing complete sets for NP" The main result is that if there is a sparse set $S \in NP$ such that $coNP ...
1
vote
0answers
29 views

Status of $BQP^{NP},NP^{BQP}$

The relation between $BQP$ and $NP$ is an open problem, while it seems that $BQP$ is somewhat lower for $NP$ than the other way round. Is the status of lowness of these problems known?
3
votes
1answer
52 views

Discrete solution space in NP-complete problems

While there are many known NP-complete problems, they all seem to be discrete in the solution space. What is the underlying principle for this?
6
votes
1answer
127 views

Is there an intuitive proof for the existence of hard functions?

I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, ``For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by ...
0
votes
1answer
30 views

Approximating the set of witnesses of a BPP algorithm

Let $\mathcal{A}$ be a randomized algorithm that decides a language $\mathcal{L}$. For each input $x\in\mathcal{L}$, we define the set of witnesses of $x$ as $W(\mathcal{A},x) = ...
-1
votes
1answer
15 views

Efficient algorithms for finding the limit of a sub-sequence [closed]

Given a sequence $A_N={a_1,a_2,a_3...,a_N}$ of real numbers, and given that there exist some sub-sequence which generated from some deterministic converging sequence. Are there any efficient ...
-2
votes
1answer
47 views

If an NP problem reduces to an NPC problem, it is NPC?

Is the following statement true? If a problem P1 is in NP and polynomial time reducible to P2, where P2 is NP-complete, then P1 is also NP-complete. Intuitively I think the answer is No because ...
0
votes
1answer
26 views

Reduction of Circuit Satisfiability to CNFSAT [duplicate]

CNFSAT is Karp reducible to Circuit-SAT by replacing all the conjunctions with AND gate, disjunctions with OR gate and negations with NOT gate. However, if we apply the same approach to Karp reduce ...
7
votes
2answers
81 views

Switching Lemma and AC0 reductions between SAT problems

Have there been efforts to show (using the Switching Lemma), for example, that SAT or 3SAT cannot have an AC$^0$ reduction to 2SAT? What are the issues or difficulties involved? SAT and 3SAT are ...
5
votes
0answers
86 views

Time Complexity of a Knapsack-derived problem

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
1
vote
0answers
64 views

A paper argumenting that P might be equal to NP [closed]

It seems like most serious computer scientists believe that P is not equal to NP, but they just do not know how to prove it. Is there any worth-mentioning paper in which an argument is made in favor ...
1
vote
0answers
29 views

How can we reduce a vertex cover problem to shortest acyclic orienatation?

I want to show that shortest acyclic orientation(SAO) is NP complete.Since vertex cover in Np complete so if vertex cover is reduced to shortest acyclic orientation then it will also be NP complete. ...
4
votes
1answer
33 views

Computational Complexity of 'Generic'/'Relaxed' Horn 3SAT

Horn 3SAT are described as the 3SAT with at most one positive literal. And its in P. What about the complexity of relaxed case of 2-Horn 3SAT i.e. Each clause is in CNF, has exactly 3 literals, with ...
2
votes
1answer
24 views

Length Preserving One way function

In the proof of existence of length preserving one way functions assuming the existence of one way functions, see Length-preserving one-way functions We need $p(n)$ to be a function which can not ...
1
vote
2answers
73 views

Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

$\mathsf{3SAT}$ in $n$ variables is an $\mathsf{NP}$ complete problem. Augment input to $\mathsf{3SAT}$ with constants $\{a_i\}_{i=1}^{n^c}$ where each constant $|a_i|<n^e$ to get an artificial ...
-3
votes
1answer
83 views

Which of these problems is not in NP? [closed]

I see one solved ex on Algorithms. Which of the following is in NP? Decision Version of TSP Array is Sorted? Finding the maximum flow network Decision version of 0/1 knapsack? ...
14
votes
3answers
157 views

Is there a complexity viewpoint of Galois' theorem?

Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...
2
votes
1answer
48 views

Reduction from 3 SAT to Monotone Exact 1 in 3 SAT

Can someone please help with a clear reduction from a 3SAT to a Monotone Exact 1 in 3 SAT. I tried searching by didn't find much.
6
votes
1answer
48 views

Relativization results in class separation

We know that $P\neq NP$ problem cannot be demonstrated by relativization because there exists oracle relative to which they are equal. Is there natural complexity classes that has been shown to be ...
3
votes
1answer
37 views

Are there algorithms with non-convex and non-concave computational complexity?

If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational ...
2
votes
1answer
61 views

Oracle for an inverse function

A. Let $F$ be a monotonically increasing real function from $[0,1]$ onto $[0,1]$. Given an oracle to $F$ and a number $y$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite ...
3
votes
1answer
61 views

What do we know about $NP \cap co-NP$?

What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it? (beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to ...
2
votes
1answer
64 views

If p(n) is a polynomial in n, then is 1/p(n) polynomially bounded?

This is part of a homework exercise. Given is an algorithm that errs with probability $\frac{1}{2}-\frac{1}{p(n)}$ for some polynomial in the input size $n$. I'm trying to prove that a polynomial ...
3
votes
1answer
168 views

Are all NP-complete languages log-space reducible to each other?

NP-complete languages are reducible to each other in polynomial time. Does this mean that they are also log-space reducible to each other? It seems as if this is true because in log-space, we can ...
1
vote
1answer
51 views

If P is equal to NP, then what happens to the problems those can be solved in polynomial time?

Suppose that an algorithm $A$ is able to solve a problem in NP in polynomial time. Does this effect the good old sorting, searching, shortest path, minimum spanning tree etc. algorithms? Can this ...
3
votes
1answer
33 views

Non-deterministic vs Deterministic turing machine to solve graph colouring

For graph coloring decision problem I mean the following: given a undirected graph, $G$, we have $GCDP(G, n)$. This returns yes instance is given if it we can color the graph with n different colors. ...
4
votes
2answers
102 views

Why is it important to solve a problem in Polynomial time, In cryptography?

I have just started to learn Cryptography. I am trying to learn "Merkle-Hellman Knapsack Cryptosystem". So, right at the beginning of the discussion, a question came in my mind: Why is it important ...
2
votes
1answer
95 views

Why does SAT not reduce to QBF?

So, I remember the professor saying that SAT does not reduce to QBF (Quantifier Boolean Formula) $QBF ::= prop|-QBF|(QBFoQBF)|\exists pQBF |\forall pQBF$ So, I guess this is not NP, since solving a ...
-2
votes
1answer
23 views

Quadratic lower bound for deciding the set of palindromes

How to prove a single tape Turing machine needs at least n squared time to decide palindrome? This is an exercise from the "computational complexity - a modern approach" book.
1
vote
1answer
87 views

PSPACE languages reducible to other PSPACE languages in polynomial space

Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?
1
vote
1answer
73 views

What is the relation between NC and P/poly?

I am unable to see a clear explanation of how the classes NC and P/poly intersect or not. (and if they do intersect then how and where? and if not then what is the proof?) I recently was attending ...
1
vote
1answer
38 views

Prove that this language is not context-free [duplicate]

I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether ...
4
votes
2answers
380 views

Is generalized XOR-SAT efficiently solvable?

I've seen how XOR-3-SAT is efficiently solvable (for instance, see the "XOR-satisfiability" section in the Wikipedia entry for Boolean satisfiability problem). I'm wondering a basic question: Is ...
2
votes
1answer
74 views

Reduce our problem to a known np-complete problem

Subgraph isomorphism We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$. Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ? (i.e. is there a subset of vertices of $G_2, V \subseteq ...
0
votes
0answers
29 views

P-time reduction A < B where B has no no-instance

I had a question to prove whether a reduction can exist $A < B$, if B has no no instances and one yes instance. I am not sure if this is too trivial. Let $A \in P$ and $Y$ be the only yes-instance ...
0
votes
0answers
11 views

Complementation in NP [duplicate]

I understand why complementing $A \in P$, hence $\hat{A} \in P$. I wanted to understand how this would work for problems in $NP$. Is the same valid for NP?
3
votes
0answers
57 views

Is integer sorting possible in O(n)?

To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem: Given a sequence of length $n$ consisting of finite integers, find the permutation where every ...
4
votes
1answer
30 views

Average case lower bound for sorting

The $\Omega(n\lg{n})$ lower bound for sorting in the comparison model is well known. Is there a similar average case lower bound for sorting in the comparison model and if so, which random ...
7
votes
1answer
130 views

Searching the space of permutations

I'm given n objects, and a set of n permutations of these n objects (out of n! total permutations). There is a true underlying permutation, which I know is one among the set of n permutations, but I ...
-1
votes
2answers
74 views

Time Complexity of k-clique problem with fixed k [closed]

My question expands on a related question on the link, Why is the clique problem NP-complete? In that post the author argued that while the $k$-clique problem is NP-complete; for a fixed $k$ the ...
0
votes
1answer
52 views

Is Weighted Vertex Cover NP-Complete? [duplicate]

I'm doing practice problems for an upcoming exam and I'm unsure if the following problem is NP-complete. If it is can you please give me a hint as to what problem I should reduce to it. I believe it's ...
1
vote
1answer
36 views

np-complete proof, turing reduction

I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know : A-> B A-> C C -> B A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for ...
3
votes
1answer
85 views

why is every self-reducible language in pspace

I understand that every self reducible language recursively queries its oracle with strings of length less than the input size. But how does that show that every such language can be solved in ...
1
vote
2answers
59 views

About being able to sample a permutation of a finite set uniformly at random [closed]

I was looking at this question. So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then ...