Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

1
vote
1answer
47 views

Upper bound for #Monotone k-SAT

(I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.) Consider a collection of $n$ Boolean ...
0
votes
0answers
38 views

Relation between Parameterized complexity and Approximation Algorithms

I want to know whether there is a relation between parameterized algorithms and approximation algorithms. Like there will exist a fpt problem for problem P iff it have some f-approx algorithm. I ...
5
votes
2answers
71 views

What theorem are these? (from Scott Aaronson's blog)

Browsing Scott Anderson's blog, I found this list of theorem. Among them are: If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a ...
4
votes
0answers
28 views

Interactive proofs for coNP languages proof clarification

I was reading a paper by Lance Fortnow and Michael Sipser. "Are there interactive protocols for co-NP languages?" Information Processing Letters 28 v5 (1988), pp. 249-251. An online version of the ...
11
votes
1answer
314 views

Why is the counting variant of a hard decision problem not automatically hard?

It is well-known that 2-SAT is in P. However, it seems quite interesting that counting the number of solutions to a given 2-SAT formula, i.e., #2-SAT is #P-hard. That is, we have an example of a ...
0
votes
2answers
29 views

EXP-complete example

Is there an explicit example of a language which is EXP-complete? Or a weaker question, i.e., is there an explicit example of a language which is proven to be in EXP but not in P? By diagonalization ...
1
vote
1answer
21 views

Is this a kind of “sketching”?

Say one is given a matrix (assume real and symmetric if necessary) and its $n-$dimensional columns be say $v_1,v_2,..,v_n$. Now is it possible to find a set of $d<n$ lower dimensional vectors ...
5
votes
1answer
52 views

Can we derandomize subexponential algorithms given P=BPP?

Under $BPP=P$ conjecture randomization does not have much power for poly time algorithms. Can we say the same about randomized subexp algorithms like number field sieve?
3
votes
0answers
20 views

A particular type of SOS hardness proof

Is there an example of a sum of squares (SOS) hardness proof where the constraint is something non-trivial (like with some polynomial constraint) rather than just imposing the the typical $x_i^2 =1$ ...
1
vote
1answer
44 views

If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ...
1
vote
1answer
91 views

Is this a well-known NP-hard problem?

Let $R = \{1, \ldots, n\}$ and $S = \{S_1, \ldots, S_m\}$ a collection of subsets of $R$ such that $R = \bigcup_{i = 1}^m S_i$ and, for $n > 3$, $$3 \leq \vert S_i \vert \leq 4 \, , \enspace i \in ...
1
vote
2answers
58 views

Is it true that P is not equal to deterministic linear space complexity class?

I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class? Is there some proof? Or should I find some algorithm which is not ...
-1
votes
0answers
14 views

How do we know that xTIME is a subset of xSPACE?

I'm just starting with Complexity and I can't figure out why do we say that xTIME is a subset of xSPACE (for x in ...
4
votes
1answer
67 views

Why there is no constraint on “Prover” in definition of $IP$?

According to the definition of $IP$ given in Sanjeev Arora and Barak there is no constraint on the running time of the "Prover" ( when "verifier" sends a message to the "Prover" and expects a message ...
1
vote
2answers
47 views

Variation of MAX 3-SAT

Suppose we are given a 3CNF, and we want to know whether k clauses from this 3CNF can be satisfied (k being any natural number)? I'm trying to think of an efficient algorithm to solve this problem. ...
0
votes
0answers
26 views

Capacitated min-k-cut problem

In the capacitated min-$k$-cut problem we are given a graph (hypergraph) with non-negative edge (hyperedge) weights. The task is then to find a partitioning of the graph's vertices into $k$ sets of ...
0
votes
1answer
12 views

what is the difference between “language” and “certificate” in complexity theory? [duplicate]

Seems like they both are set of strings for which the problem returns "yes" in decision problems. P class is consists of problems so we can only say a problem is in P. But we sometimes say that a ...
2
votes
1answer
46 views

Is the unweighted vertex cover problem equivalent to its weighted version?

Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq_\mathrm{m} ...
0
votes
1answer
29 views

Log reduce PATH to DISTANCE-PATH

An instance of PATH is given by where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t. DISTANCE-PATH is similar, but with an extra requirement ...
1
vote
1answer
54 views

Reduce set partition search to decision?

I'm a little lost and don't know how to approach this problem. Show the partition search problem can be poly-time reduced to the partition decision problem, the partition decision problem takes ...
2
votes
0answers
41 views

Kleinberg Rubinfeld Short Paths in Expander Graphs for Hypergraphs [migrated]

In 96 Kleinberg and Rubinfeld in "short paths in expander graphs" showed that for any $\Delta$-regular $\alpha$-expander graph ($\alpha >0$) $G$ on $n$ nodes, if $H$ is any graph on at most $cn/ ...
1
vote
0answers
28 views

(Why) is there no complexity class for linear space (O(n))? [duplicate]

tldr: I'm looking for any general information about the linear space complexity class. e.g. is there a complete problem for it? the Quantified Boolean Formula (QBF) problem is a P-space complete ...
1
vote
0answers
21 views

About the complexity of learning probabilistic graphical models

I guess that one way of measuring the complexity of learning a joint probability distribution is as its "sample complexity" (which is also sometimes known as its "distributional learning complexity"?) ...
3
votes
2answers
33 views

How can we use the FPTAS for problem B to solve problem A

Given an optimization problem A which is NP-complete, and can be polynomially reduced to another optimization problem B which is also NP-complete. If we use an FPTAS to solve the reduced problem B' (A ...
1
vote
1answer
50 views

Why are problems in P easy and other problems not

Problems in $P$ have polynomial time algorithms. Problems in e.g. $NP-complete$ are only solvable in "probably exponential time" (Shen Lin's PET). Problems in $P$ are considered easy while others ...
-1
votes
1answer
48 views

Problem in computational complexity (superior class)

Say that a class $C_1$ is superior to a class $C_2$ if there is a machine $M_1$ in class $C_1$ such that for every machine $M_2$ in class $C_2$ and every large enough $n$, there is an input of size ...
1
vote
1answer
40 views

Why is ZPP = RP ∩ co-RP?

I am trying to prove the theorem that ZPP = RP $\; \cap \; co-RP$. If $L \in \; \subseteq RP \; \cap \; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, ...
1
vote
0answers
18 views

A question about SOS duality

Let us start with the optimization question, \begin{eqnarray*} min \{ c \vert c - f \in SOS_d \} \end{eqnarray*} for some function $f : \{0,1\}^n \rightarrow \mathbb{R}$ and $SOS_d $ being the cone ...
7
votes
3answers
474 views

The difference between theoretical complexity and practical efficiency

If I have this pseudocode: for i=0 to n/2 do for j=0 to n/2 do ... do anything .... The number of iterations is $n^2/4$. What is the complexity of ...
1
vote
0answers
21 views

Difference between graph-partitioning and graph-coarsening

What is the difference between graph-partitioning and graph-coarsening with respect to scale-free networks? I am trying to analyze graphs generated using the data from social networks. Do both the ...
3
votes
1answer
44 views

A clarification on $PP$

Wiki in https://en.wikipedia.org/wiki/PP_(complexity) says "a PP algorithm is permitted to do something like the following: On a YES instance, output YES with probability $1/2 + 1/2^n$, where n is ...
4
votes
2answers
61 views

On certificates in BPP (avoiding majority vote)

Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output. However if the problem $\Pi$ is also in $NP$ ...
5
votes
3answers
1k views

Complexity of sorting a 1-sorted array

A $k$-sorted array is one in which every element is at most distance $k$ from its position when the array is sorted. The complexity of sorting such array is $O(n\log k)$. But if $k=1$, then $\log ...
1
vote
1answer
72 views

Reducing co3SAT to UNIQUE-SAT

I am having trouble with this problem: Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq_p UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique ...
0
votes
2answers
64 views

Polynomially reducing NP-Complete problem clarification

I am having trouble solving the following question. I am given a following problem X: Given a graph G, we want to know whether there is an edge e in G such that G − e is 3-colorable. I want to show ...
1
vote
1answer
35 views

A function computable using a circuit of size $10s$ but not of size $s$

I'm studying Computational Complexity and I have stumbled upon the following question which I have no idea how to even start proving. I would appreciate any help. Prove that for every function ...
4
votes
1answer
522 views

Give a specific case where calling a polynomial time function n times gives an exponential time algorithm

We were asked this question in exam and I am not satisfied with the answer the teacher gave. Let me justify my point of view. Let there be a polynomial time function having time complexity $n^{c_1}$. ...
0
votes
0answers
51 views

Complexity of active set method for Quadratic Programming

The Quadratic Programming problem is as follows: $$\min_x \{\frac12x^THx+x^Tg\}$$ $$Ax\le b$$ where $H$ is symmetric and positive semi-definite. What is the complexity of the active set method for ...
0
votes
0answers
14 views

Want to show that if P = NP, then P = NP = CoNP [duplicate]

I want to show that if P = NP, then P = NP = CoNP. Essentially, I want to show that if the set of problems which can be solved in polynomial time is exactly the set of problems which can be checked in ...
2
votes
1answer
27 views

Approximating all independent sets of size k in a graph

Given an undirected graph, I need an algorithm that outputs all the independent sets of size >= k (constant) in the graph. I know the problem is NPC, and I do not want to use the exponential ...
3
votes
3answers
50 views

is little-o notation correct after being powered by a number?

I just wanted an example in which the equation given below is not correct. $f(n) = o(g(n)) \Leftrightarrow 2^{f(n)} = o(2^{g(n)})$
4
votes
1answer
73 views

See that P$^{NP}_{||} = P^{NP}_{O(\log n)}$

I'm trying to prove that P$^{NP}_{||} =$ P$^{NP}_{O(\log n)}$ where $n$ is the length of the input. So, to see that polynomially many non-adaptive queries to a problem in NP can do as much as ...
1
vote
1answer
30 views

Reduction variation for the q-coloring problem

I'm trying to prove that $q$-COL $\leq^P_m q$-COL$_{2q-1}$, where $q$-COL$_{2q-1}$ is the restriction of the q-coloring problem to graphs of maximum degree $2q-1$. Now, it seems fairly obvious "if you ...
3
votes
1answer
33 views

How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$

Following is a theorem from Sanjeev Arora and Boaz Barak I am unable to prove : If $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \Sigma^p_2$. The previous similar theorem was ...
1
vote
1answer
31 views

Complexity for merging 3 sorted arrays using this specific algorithtm

During an interview I was asked to calculate the big theta complexity for the following algorithm that receives 3 sorted arrays of variable size and returns a new array which has the elements of the ...
1
vote
1answer
77 views

In this proof that sokoban+ is pspace complete, how does the gadgets register the fact that a cell of the turing machine has changed?

I´ve been reading the paper "SOKOBAN and other motion planning problems" by Dorit Dor and Uri Zwick. This is a link to the paper: Sokoban+ is pspace complete In the paper, they proved that a ...
1
vote
2answers
48 views

Reduction between two decision problems

We are given two decision problems: $Q_1\colon I_1\to\{0,1\}$ and $Q_2\colon I_2\to\{0,1\}$. By definition, if there exists a function $f\colon I_1\to I_2$ such that for each $x\in I_1$ we have ...
0
votes
1answer
9 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...
1
vote
1answer
49 views

Universal memcomputing machines (UMM)

This paper on memcomputing seems like a really big deal, but it doesn't seem to be particularly popular. They prove that their UMM can solve NP problems in P, although they don't claim P = NP. In ...
2
votes
1answer
25 views

A certain submatrix of the correlation polytope

I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf Firstly given that the author wanted to look at quadratic ...