Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

1
vote
1answer
9 views

A particular complexity

Whats is the name for a complexity like $n^{\log \log n}$ ? Is this exactly subexponential, or less than that ?
0
votes
0answers
14 views

How does hashing achieve sketching?

Given a sequence $x \in \{ 1,2,3...,\vert \Sigma \vert \}^*$ one wants to create a sketch of it say $s(x)$ of size $\frac{2c}{3}k (ln^2 k)$ bits. And that seems to be achieved as follows, pick at ...
6
votes
0answers
49 views

Is the closure of P under e-free homomorphisms equal to NP?

The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations ...
1
vote
1answer
46 views

Is this problem NP-hard?

Good day. Subset sum selection problem is NP-hard. I trying to solve following problem: Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value. Solution: subset of ...
1
vote
1answer
20 views

Ordered knapsack problem?

I'm trying to find the name of this problem, and with it a reasonable algorithmic solution. Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights ...
-1
votes
0answers
20 views

How to transfer tsp to factorization?

So we know that travelling salesman problem is NP-Complete, that means if we solve it, we can solve factorization problem in the same amount of time. How do we do it though?
3
votes
1answer
56 views

Intuition for PH notation in Arora-Barak's Computational Complexity

For the definition of polynomial hierarchy: $x \in L \Leftrightarrow \exists u_1 \in \{0, 1\}^{q(|x|)}\forall u_2 \in \{0, 1\}^{q(|x|)} \cdots Q_i u_i \in \{0, 1\}^{q(|x|)} M(x, u_1, \ldots, u_i) = ...
2
votes
1answer
17 views

Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of ...
1
vote
1answer
75 views

Can Circuit Value Problem or HORN-SAT be reduced to PATH problem?

PATH = {(X,R,S,T) | exists an x in S that is admissible} Where R is a relation of X x X x X, S is a unary relation of X and T is a unary relation of X aswell. An x element of X is admissible if it is ...
1
vote
1answer
65 views

How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs? [on hold]

As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable? This is not a "technical" ...
4
votes
1answer
40 views

What usage is the delta defined in the polynomial hierarchy?

At the Wikipedia page, the polynomial hierarchy also defines the following: $\Delta_0^\text{P} = P$, $\Delta_i^\text{P} = \text{P}^{\Sigma_{i-1}^\text{P}}$ However, the only usage of this anywhere ...
0
votes
0answers
12 views

Arthur-Merlin protocol to decide a set size

Please look at the example here at the bottom of page 3, http://www.cs.nyu.edu/~khot/CSCI-GA.3350-001-2014/sol3.pdf Here it seems that the set whose size Arthur is trying to approximate is known in ...
1
vote
1answer
38 views

About a particular use of hashing

Look at the last problem on page 2 here, http://www.cs.nyu.edu/~khot/CSCI-GA.3350-001-2014/sol3.pdf All one wants to do is to convert a $x \in \{ 0,1\}^n$ into a $y \in \{0,1\}^k$ . Then just a ...
3
votes
1answer
45 views

Is the minimal number of colors needed to color a graph some fixed number?

Consider to following decision problem: Input: Undirected graph $G=(V,E)$ Question: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices ...
6
votes
1answer
72 views

TM recognizing $0^n1^n$ requires Ω(log n) space

I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires $\Omega(\text{log }n)$ space. I believe this can be ...
-2
votes
1answer
30 views

Is a single tape Turing machine equal in power to a Turing machine that can only move right? [duplicate]

I assume no, because a Turing machine that can only move right feels like it is not a Turing machine. But, I wonder if I can add a Reset to the right moving Turing machine that resets the what head ...
3
votes
1answer
386 views

Good introduction to Turing's work and complexity theory?

I'm currently an undergrad whose been amazed by what Turing has done for the world. I know there are plenty of other amazing individuals, but Turing's work specifically has always sounded the most ...
2
votes
1answer
59 views

Proof of $P^{\text{#}P} = P^{PP}$

I was reading this article on the complexity class $PP$. In the fourth paragraph there is a claim that $P^{\text{#}P} = P^{PP}$ and that it can be proved using binary search. Can anyone please ...
5
votes
1answer
35 views

Question on NP $\cap$ coNP

I'm struggling with a past paper question and would appreciate any hints: Suppose $L_1, L_2 \in $ NP $ \cap $ coNP and $L_1 \oplus L_2 = \{ x : x $ is in exactly one of $L_1 $ or $ L_2 \} $. Then ...
3
votes
1answer
23 views

How to state that a complexity bound does not depend on a given parameter size?

I am often ill at ease with Landau (Big O) notation, because it seems often to be abusing mathematical notation. The best example is the use of the equal sign to express a set membership. And this can ...
2
votes
1answer
110 views

How to improve my these specific math skills? [closed]

I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite ...
6
votes
1answer
72 views

Is there a continuous hash?

Questions: Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$? Can we add an efficiently computable closeness predicate which given $h_k(x)$ and ...
0
votes
0answers
14 views

More about the ESP tree

In this previous question I had asked about the intuition behind looking at the ESP tree. One place where it is used is to construct an approximation of arbitrary distance functions $d : [m]^n ...
2
votes
1answer
26 views

How to read $NC^1\subset L \subset NL \subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?

The (complexity zoo) description of $NC^1$ says that it is contained in $L$, i.e. $NC^1\subset L$. The description of $SAC^1$ says that it is equal to $LOGCFL$$/poly$, i.e. $SAC^1=LOGCFL/poly$. The ...
-1
votes
1answer
26 views

Use Rice's theorem to prove the following is undecidable

Given the language $L=\{\alpha \mid M_{\alpha}(x)=x^3$ for all $x\in\{0,1\}^*\}$. Prove using Rice's theorem that $L$ is undecidable. Rice's theorem: Let $P$ be a set of all computable functions ...
-2
votes
0answers
19 views

How to formally show that $f(n) = o(g(n))$ [duplicate]

Given $f(n)=n^{100}$ and $g(n)=2^{\frac{n}{100}}$, I can tell that $f(n)=o(g(n))$ mainly because $n^c=o(2^n), \forall c$. But how can I formally show that $f(n)=o(g(n))$. My attempt at this question ...
1
vote
1answer
33 views

Complexity terminology

What is the terminology used for speaking about complexity, when we don't study it asympotically (but exactly) ? Thank you
2
votes
1answer
30 views

Is it possible that low-resource Turing Machines can always “usually” agree with high-resource Turing Machines

Say that a language $L$ is a $f$-approximation of a language $L'$ if, for all input lengths $n$, $L$ and $L'$ agree on at least a fraction $f$ of the inputs. It is known that there are problems in ...
1
vote
1answer
30 views

Can well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE?

I read that visibly pushdown languages are supposed to model the typical simple formal languages like XML better than deterministic context free languages. The visibly pushdown languages can be ...
1
vote
1answer
44 views

What's wrong here, or, is CNF to DNF conversion in o(exp(n))?

I've been thinking about conversion from CNF to DNF. Assume a "worst case" CNF formula with $k$ disjunctions, each containing exactly $l$ elements and no variable is used twice. Example with $k=3$ and ...
2
votes
1answer
33 views

Probabilistic algorithm with two-sided error

I am currently studying probabilistic algorithms and came across three major complexity classes: BPP: worst-case polynomial time, two-sided error RP: worst-case polynomial time, one-sided error ZPP: ...
0
votes
0answers
8 views

Removing the acceptance error from AM

Typically the AM class is defined with error upper bound of 1/3 for deciding both the situations of the membership question being true or false. But curiously enough for the situations when the ...
2
votes
1answer
47 views

Cycles in hardness of ST-CON for the class NL

It seems to me that the problem of $s$, $t$ connectivity in a DAG should still be NL-Complete. I am aware that ST-CON without the DAG restriction is complete for NL, so obviously the DAG restriction ...
3
votes
1answer
40 views

Proving NP completness without reductions

What methods are there to prove a language is NP-complete? I already know the reduction method, but are there more sophisticated/advanced methods to prove this?
1
vote
1answer
19 views

How does derandomization of 3SAT work via conditional expectations?

Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that a random assignment of values will satisfy it with probability 7/8 But I do not understand how ...
3
votes
1answer
30 views

What is the rigorous definition of an efficient algorithm that $\epsilon-refutes$ random 3CNF formulas

I recently asked a similar What does "refuting random 3CNF" formulas mean?, however, I'd like to address it in a more mathematically precise setting. In that paper, on page 5, it talks ...
5
votes
1answer
41 views

bounded length CoNP proof

Question: Let $A \subseteq $ {0,1}$^* $ be a language which satisfies $|A \cap ${0,1}$^n|=n^3 $ for all $n\ge 10$ Prove that $A \in NP$ implies $A \in coNP$. Thoughts I've been having difficulty ...
1
vote
1answer
32 views

Are there any theorems/formulas that apply to the height of comparison trees?

I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an ...
3
votes
2answers
62 views

What does “refuting random 3CNF” formulas mean?

Intuitively, recall what 3CNF formulas mean: Its a boolean formula with conjunctive normal form (i.e. formula of ANDs of clauses with ORs) with no more than three variables per conjunct. I was ...
1
vote
1answer
18 views

Are there two kinds of polynomial hierarchy collapses?

It seems to me that there are two different situations which get called ``PH collapse", (1) That $\exists i \geq 1$ s.t $\Sigma_i ^p = \Sigma_{i+1}^p$ (2) That $\exists i \geq 1$ s.t $\Sigma_i^p = ...
6
votes
1answer
32 views

Hardness of a problem related to set cover

Suppose $C_1, \ldots, C_m$ are subsets of $\{1, \ldots, n\}$. The goal is to find the smallest subcollection of $C_1, ..., C_m$ such that each element of $\{1, \ldots, n\}$ appears at least $k$ times ...
3
votes
1answer
28 views

What is the decidable language in $P/poly$ but not in $P$?

Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$
5
votes
0answers
45 views

Is the compuation of a minimal correction subset (MCS) $FP^{NP}$-hard? [migrated]

MCS problem: Given a set $\phi$ of Boolean clauses. Find a minimal correction subset (MCS) $M\subseteq\phi$ such that: $\phi\setminus M$ is satisfiable and for all $c\in M$ holds $\phi\setminus ...
1
vote
1answer
53 views

Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?) [duplicate]

I've been trying to wrap my head around Co-NP, and how it's different to NP, but I am having some trouble. Co-NP is defined by Wikipedia as this: "A decision problem $\mathcal{X}$ is a member of ...
0
votes
0answers
15 views

Subset product problem for powers of 2

We know that the "subset product problem" is NP-complete, as Gary and Johnson mentioned in their book, and the proof is by reduction from X3C. I wonder if we can prove that this problem, i.e., the ...
3
votes
1answer
34 views

Lower bound for maxima on 2D plane

Given $n$ points $(x_1, y_1), \ldots, (x_n, y_n)$ on a 2-dimensional plane. A point $(x_1, y_1)$ dominates $(x_2, y_2)$ if $x_1 > x_2 \land y_1 > y_2$. A point is called a maxima if no ...
2
votes
1answer
21 views

How does one change the probability bounds in probabilistic complexity classes without changing the class?

I see this theorem whose proof is not clear to me : "Let $L \subseteq \{0,1\}^*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \{0,1\}^*$ and $Pr[ ...
2
votes
2answers
36 views

Difficult Cases for 3MaxSAT and 3SAT Approximation Algorithm

Its known that a polynomial time approximation algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP. Its also experimentally known that 3SAT has the most difficult known cases when the ...
2
votes
1answer
93 views

$P \neq NP$ and determinism

Suppose $P \neq NP$. Does it imply that there exists some superpolynomial time bound, such that any $NP$-complete problem, like SAT, can be used to simulate an arbitrary deterministc Turing Machine ...
2
votes
1answer
20 views

Sensitivity versus degree

Given boolean function $f$, let $F$ denote the unique multiaffine real polynomial representing $f$. Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$ where $x^i=x\oplus\Bbb 1_i$ ...