Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

-1
votes
1answer
96 views

How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?

I am studying for NP problems. To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT ...
1
vote
1answer
35 views

*non-uniform* $ACC^0$ and above classes

$NEXP$ smallest class above $ACC^0$ that we know is separated from $ACC^0$. We do not know if either $NP$ or $P/poly$ is in $ACC^0$. Suppose every problem in $NP$ can be solved in polynomial time ...
1
vote
2answers
107 views

Context free languages belongs to NTIME(n)?

As the question states, how do we prove that for every L ∈ L2 (context-free class of languages) is true that L ∈ NTIME(n)? Can anyone point me to a proof or outline it here? Thanks!
1
vote
1answer
28 views

On $SUBEXP$, $PP$ and $P/poly$

Complexity zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dtime states $DTIME(f(n))$ with $PP$ oracle is not in $P/Poly$ if $f(n)$ is superpolynomial. We know ...
1
vote
1answer
44 views

Query on consequences of $\mathsf{P=BPP}$

We know $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$ or permanent does not have polynomial sized circuits. However permanent needs superpoly circuits imply $\mathsf{NEXP\not\subseteq ...
-1
votes
1answer
30 views

P is closed under power of integer

I'm new in this area of complexity and I'm trying to get into it by understanding basic proofs. I want to prove that if $L\in P$, so $L^k\in P$, where $k$ is non-negative integer. How to prove it in ...
0
votes
0answers
98 views

Reduction from 3-Partition to a cutting problem

My problem is the following: Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$. Output: $n$ sets of 3 numbers Task: Cut the $b_i$'s into $3n$ integers ...
2
votes
1answer
43 views

Difference between $\mathsf{SIZE}(n^k)$ and $\mathsf{P/poly}$

In the Wikipedia page on the Karp–Lipton theorem it is mentioned that $$\Sigma_2\not\subseteq\mathsf{SIZE}(n^k)$$ (which is known) is not same as $$\Sigma_2\not\subseteq\mathsf{P/Poly}$$ (which ...
2
votes
0answers
55 views

What is the complexity of classification with SVMs?

I'm interested in how fast SVMs can classify new data with $c \in \mathbb{N}_{\geq 2}$ classes and $n \in \mathbb{N}_{\geq 1}$ features. Example for Neural Networks For neural networks, this depends ...
1
vote
0answers
24 views

Do we have to overcome any barriers for a proof of $VP\neq VNP$ proof?

Does the same barriers of relativization, natural proofs and algebrization affect a possible $VP\neq VNP$ proof? How do existing strategies try to overcome these?
0
votes
0answers
22 views

Are there any classes of functions whose definitions can be easily procedurally generated and have implementations easily procedurally checked, but

Are there any classes of functions whose definitions can be easily procedurally generated and have implementations easily procedurally checked, but for which valid implementations are difficult or ...
2
votes
3answers
103 views

Efficient algorithm to decide if a location is reachable

I am designing a game solver. I have a binary $m*n$ Matrix, where $0$ stands for a free space, while $1$ stands for an occupied space. In the game we move a ball that we will call $x$. The ball can ...
3
votes
2answers
78 views

When proving NP-completeness do I only need one instance of a problem or all of them?

I saw a proof of reduction of hamiltonian path to spanning tree with inner vertices having degree of k. The person, who proved it, constructed a spanning tree from a hamiltonian path, basically ...
2
votes
2answers
114 views

Longest cycle in a digraph

Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem? Do we know its ...
6
votes
1answer
138 views

Sum of all products of subarrays

For any three-dimensional array $A$ of size $n_1 \times n_2 \times n_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod_{i_1 = 1}^{n_1} \prod_{i_2 = 1}^{n_2} \prod_{i_3 = 1}^{n_3} ...
0
votes
0answers
25 views

DISTINCT 3-PARTITION with all integers between $B/4$ and $B/2$

In the definition of 3-PARTITION of Garey&Johnson, the instance is a set of $3m$ integers such that the sum of all these integers is $mB$ and such that each integer is strictly between $B/4$ and ...
3
votes
1answer
32 views

Is there a name for the problem of spatially organizing a graph as to minimize total edge length?

The problem is that of spatially (with or without a fixed spatial dimension) organizing a graph so that each node becomes a cell in a grid, and each edge becomes a line, such that the total combined ...
-2
votes
2answers
66 views

How to prove P ⊆ Co-NP

My approach Let L ∈ P $\exists$ Turing Machine $M_1$ which decides L. We can easily construct $M_2$ which decides $\bar{L}$ $\bar{L}$ ∈ CO-NP $\implies$ P ⊆ Co-NP I'm not sure ...
1
vote
0answers
46 views

Why is it NP-hard to learn a disjunction of k variables as a disjunction of fewer than k log n variables?

I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection by R. I. Arriaga and S. Vempala (2006): Further, it is NP-hard to learn a disjunction of k ...
0
votes
0answers
43 views

If EXP = NEXP, can we say anything about P and NP? [duplicate]

I found one older question asked about this but without any responses.
1
vote
1answer
59 views

Do polynomial reduction functions work both ways?

For example to prove 3-Sat ≤p Independent Set do I just have to prove this theorem: Theorem- Formula F is satisfiable IFF graph has an independent set. If I have to prove it this way does this also ...
5
votes
1answer
54 views

Certificates and NP?

My book says a language is in NP if it can polynomially verified if a string belongs to the language with a certificate. It puts no restrictions on what the certificate can be. For instance, for SAT, ...
0
votes
0answers
20 views

Why does not the complement of a language belonging to class NP, also belong to NP in general? [duplicate]

I know that complement of a language belonging to NP, does not necessarily belong to NP. I came across the example $L= \{\langle G,s,t \rangle | G \text{ is a directed graph and there exists a ...
5
votes
4answers
1k views

Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and ...
6
votes
1answer
163 views

Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

I read a theorem which states that: If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant ...
4
votes
1answer
32 views

Logarithmic Randomness is Necessary for PCP Theorem

I am trying to proof the following statement: If $ {\rm SAT} \in {\rm PCP}[r(n),O(1)]$, where $ r(n)=o(\log n)$, then ${\sf P}={\sf NP}$. Here are my ideas for the proof: It can be easily worked ...
0
votes
1answer
50 views

NP-complete promise problems? [closed]

Are there any good examples of promise problems that are NP complete?
1
vote
1answer
64 views

NP to SAT. How does it works? [closed]

Let's start here: It is said that all NP problems can be reduced to SAT(boolean satisfiability problem). To be more accurate to Circuit SAT, because all decision problems like NP should end up with ...
4
votes
0answers
37 views

Complexity class of finding the number of walks of length $k$ that have different vertex sets

Vertex set $A$ is of the form: $A = \{(v_1,r_1),(v_2,r_2),...\}$ where $v_1 \in V$ and $r_1$ refers to the number of times $v_1$ is reached in some walk and $v_j \neq v_i$ whenever $i \neq j$. ...
0
votes
1answer
47 views

How can you check if a 2SAT problem has a bad loop

im trying to figure out why this is true The clauses {a,b}, {b,~c}, {c,~a} constitute a 2SAT problem with an implication graph without bad loops. Can someone show me how to illustrate this and ...
1
vote
1answer
28 views

Definition of complexity classes?

My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$): $$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an ...
0
votes
0answers
28 views

Natural problems ٍsolvable in quasi-polynomial time and have good characterization

In light of Babai's proposed quasi-polynomial time (QP) algorithm for graph isomorphism problem and the belief (under widely accepted derandomization conjecture ) that GI is in coNP, I got interested ...
1
vote
1answer
14 views

What set of primitive operations are assumed to be constant time in complexity analyses?

Different set of primitive operations lead to different complexity of certain problems. For example, sorting by comparison is only O(N*log(N)) if one assumes both ...
6
votes
2answers
263 views

How to prove P$\neq$NP?

I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point. We can show that P $=$ NP if and only if we can design an algorithm that solves any ...
1
vote
1answer
38 views

Can computation models be categorized in terms of efficiency?

It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other ...
13
votes
2answers
962 views

Why is factoring large integers considered difficult?

I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ ...
1
vote
0answers
18 views

NP-Complete: reduce “L” the language such as circuits C1 and C2 compute the same function

I'm trying to reduce the NP-Complete language "CIRCUIT-SAT" (C is a boolean circuit that is satisfiable) to my language L, but my classmates are pointing out that i'm actually doing the opposite, ...
2
votes
0answers
21 views

Is unique MAX-2SAT NP-Complete?

MAX-2SAT is NP-Complete. If the solution is stipulated to be unique, is MAX-2SAT still NP-complete?
-2
votes
1answer
78 views

Reduction from 3SAT [closed]

You are given a directed acyclic graph G = (V, E) in which each node has one “left” out-arc and one “right” out-arc, with a distinguished source node s and sink node t. You are also given a list of ...
2
votes
1answer
46 views

What does it mean when a time complexity has another time complexity within it?

Sometimes, when reading about algorithms or other theoretical topics, I see time complexities that include other time complexities within the expression. For instance, "the best fixed-parameter ...
1
vote
1answer
34 views

Time complexity - least upper bound

I know that Big $O$ notation is used to describe the upper bound of running time of an algorithm, if we consider time complexity of that algorithm. However, I'm not sure why the following is not ...
0
votes
0answers
44 views

Polygon casting - Removing from mold by rotation

How can I show that the problem of finding a center of rotation that allows us to remove P with a single rotation from its mold can be reduced to the problem of finding a point in the common ...
1
vote
3answers
331 views

What does it mean for a problem to be both NP hard and coNP hard

I have a faint notion of what NP hard is (that a problem is legit difficult 3 SAT for example). I have forgotten what coNP hard, and Wikipedia tells me that the complement of coNP hard is NP ...
2
votes
2answers
38 views

Hardness of approximation: what decision problem is hard exactly?

Just a question for personal comprehension. Consider the following statement: It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 < \epsilon < 1$. ...
2
votes
1answer
210 views

Why do puzzles like Masyu lie in NP?

The puzzle is made up of (n x n) squares so when taking the problem the input size would be n. Rules of Masyu: The goal is to draw a single continuous non-intersecting loop that properly passes ...
5
votes
2answers
447 views

NP complete language having no Polytime decidable superset

Is there an NP complete language having no polytime decidable superset (apart from the set of all strings)?
1
vote
1answer
52 views

Is HAMPATH in NL/L?

I know HAMPATH is NP complete problem. But is there a way to tell if it is either a NL or L problem? I tried searching a lot of places online but it feels like I am going nowhere. Thanks in advance ...
2
votes
0answers
84 views

Subset minimizing the cost of a one-sided matching, involving preference orders

We're given a set of items $A=\{1,\dots,m\}$ and a set of people $B=\{1,\dots,n\}$. Each person has a preference ordering for the items in $A$. Each item in $A$ has a specific positive cost for each ...
0
votes
1answer
34 views

weighted subset exchange question

Assume there is a set {1,...,n} of person. For each person i, a set $A_i$ of items are available for exchange. A is the set of all items. The value of item j to person i is $v_{ij}$ and assume all ...
0
votes
1answer
29 views

Finding subset such that one sum is more than target and another sum is less

Consider the following problem: Given positive integers $a_1,\ldots,a_n,b_1,\ldots,b_n,A,B$, does there exist a subset $S$ of $\{1,\ldots,n\}$ such that $\sum_{i\in S}a_i\geq A$ and $\sum_{i \in ...