Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

2
votes
0answers
5 views

Switching Lemma and SAT problems

Any experts here on the Switching Lemma? 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 ...
1
vote
0answers
58 views

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

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
22 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
25 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
16 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
64 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
77 views

Which of these problems is not in NP? [on hold]

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? ...
7
votes
2answers
80 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
30 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
36 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
35 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 ...
3
votes
1answer
54 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
40 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 ...
0
votes
0answers
12 views

What are the known NP-hardness or optimization results about spectrum of matrices? [closed]

Like for symmetric $d-$regular matrices over 0/1 or 0/1/-1 what are some known optimization results about their possible spectral radius or spectral gap? [..I am calling a symmetric matrix to be ...
3
votes
1answer
156 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
42 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
26 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
82 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
62 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
18 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
76 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?
-4
votes
0answers
16 views

Reducing 3-SAT to HCP [closed]

I am looking for some visual material and explanation of this reduction: 3-SAT < HCP (Hamiltonian Circuit Problem) What are the key steps in this reduction? Is there any strategy to tackle this ...
1
vote
1answer
62 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
30 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
359 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 ...
-3
votes
0answers
47 views

Is this problem NP complete?

Given $\{a_i\}_{i=1}^n\in\Bbb N^n$, is there a $v\in\Bbb N^n$ such that $$\prod_{i=1}^na_i^{v_i}\in[L,U]$$ where $(L,U)\in\Bbb N^2$? Each of $a_i,v_i,L,U$ has $O(n^c)$ bits with some fixed ...
2
votes
1answer
70 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
27 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
53 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
27 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 ...
6
votes
1answer
122 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
50 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
43 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
35 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
80 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
55 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 ...
5
votes
1answer
145 views

Lower bound for finding majority element in a sorted array

Suppose $A$ is a sorted array with $n$ elements. I want to know whether we can determine if there are majority elements in $A$ with time complexity $O(1)$. Recall that a majority element of $A$ is ...
7
votes
1answer
257 views

DNF to CNF conversion: Easy or Hard

In relation to the thread CNF to DNF — conversion is NP Hard (and a related Math thread): How about the other direction, from DNF to CNF? Is it easy or hard? On Page 2 of this paper, they seem to ...
0
votes
1answer
17 views

About having analytic control over any algorithm which finds perfect matchings.

A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a ...
6
votes
0answers
165 views

Sokoban with only $k$ boxes

Note: I have posted a hugely expanded version of this question on cstheory. Since a Sokoban instance with only $k$ boxes has at most $n^{O(k)}$ possible states, the problem lies in ...
-3
votes
0answers
25 views

EQ NFA p-space complete

Who originally proved that eq nfa is p-space complete. Could someone provide me with a reference to the paper where it was originally proved.
1
vote
0answers
29 views

Open problems in complexity theory [closed]

I am looking for open problems in complexity theory that an undergrad might have any possibility of tackling.
3
votes
1answer
58 views

About codes over $\mathbb{F}_2$

I was looking through these notes but I am not sure I can locate the answer to these questions of mine - it would be great if someone can just even point out what to look for! So any set of binary ...
2
votes
0answers
37 views

Disco Zoo Complexity

A popular mobile game, DiscoZoo, is about "rescuing" animals from a 5x5 grid of cells. Each animal represents a unique pattern (some have 3 cells, some have 4). The object is that, given this 5x5 ...
0
votes
0answers
22 views

How many processors does STCON need on a PRAM?

I'm trying to understand why the s-t connectivity (STCON) problem is in NC. In order to be in NC, a problem must have an algorithm that is O((log n)^c) time and O(n^k) processors where c, n are ...
2
votes
2answers
65 views

Consequences of $NP=coNP=BPP=RP$

What is complexity theoretic implication of following possibilities - $NP=coNP=BPP=RP$ or $coNP\neq NP=BPP=RP$ (consensus is these seem impossible)?
2
votes
0answers
122 views

PSPACE completeness, with different kinds of reductions

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction. This class is known as PSPACE-complete. ...
5
votes
1answer
104 views

Reduction from Vertex Cover to Polygon Cover

Polygon Cover: Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$. Output: True if and only if there exists a subset in $S$ of at most $k$ ...
2
votes
1answer
31 views

Constructing solution to 3SAT formulas using oracle queries [duplicate]

I'm interested in 3SAT and querying an oracle. Suppose we had an oracle that can decide, on an input boolean formula $\phi$, whether there exists any assignment to the variables that makes the formula ...