Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

1
vote
0answers
20 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ and a number $k$. Question: Is there a cut of capacity at most $k$? I can't really find anything. ...
3
votes
0answers
18 views

Does $\#W$[1]-hardness imply approximation hardness?

Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$. Assume that $\Pi$ is ...
7
votes
1answer
57 views

Does #$P$-Completeness imply approximation hardness?

Let $\Pi$ be some counting problem which is known to be #$P$-Complete. Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
5
votes
0answers
90 views

Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
6
votes
4answers
188 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
-3
votes
0answers
18 views

communicational complexity calculation [on hold]

i need help regarding communication complexity of security purpose algorithm. from my basic knowledge, i think algorithm with lower computational complexity is acceptable like O(n) > O(n^2); but what ...
2
votes
1answer
58 views

Reduce Set problem to SAT

So the problem is, given some set $M = \{x_1,x_2,\ldots,x_n\}$ and a set of subsets $S = \{S_1, S_2, \ldots, S_m\}$ where $S_i \subseteq M$. We want to find some set $X \subseteq M$ such that $|X| \le ...
-1
votes
1answer
32 views

Is finding negative cycle vertices NP complete?

I was trying to find all the negative cycle vertices using the Bellman–Ford algorithm using this paper solution 7.1(b) in $O(V)$ by tracing back the predecessor subgraph.It is also stated in ...
1
vote
1answer
42 views

What are the current known implications of the complexity of Integer Factorization?

According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP. However, do we know any other ...
0
votes
1answer
22 views

What is an oracle separating IP and PSPACE?

I saw this link on cstheory: http://cstheory.stackexchange.com/questions/6634/is-there-an-oracle-that-separates-two-complexity-classes-known-to-be-equal but it did not provide specific details. Can ...
7
votes
2answers
134 views

Generating a set of minimal-length strings that, together, invoke every production of a context free language

Problem (tl;dr) Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once. How and how fast can it be done? Background I'm working on a ...
3
votes
1answer
76 views

How to challenge Hutter's algorithm?

For a given sufficiently strong formal axiomatic system $\mathsf{F}$ (like $\mathsf{PA}$ or $\mathsf{ZFC}$) and any given function $p^*(x)$ that can be specified within the formal system $\mathsf{F}$, ...
7
votes
1answer
95 views

Can an NP-hard problem be polynomial on average?

I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this? If $P \neq NP$, can there be an algorithm solving an ...
3
votes
1answer
134 views

Are there are problems in NP that have been shown to be not NP-complete but it is still not known if they are in P or not?

I am not talking about NP-indeterminate class because those problems have to be shown to not exist either in P or NP-complete class and existence of such problems proves P!=NP. I am interested to know ...
3
votes
1answer
56 views

A Reduction from XORSAT to 2-SAT

Does anyone know of a non-trivial reduction from XORSAT to 2-sat since they are both in P? (By non-trivial I mean one that does not just solve the instance of XORSAT and map it to a fixed instance of ...
1
vote
1answer
27 views

Is random access allowed in the Bit Complexity model, or is it just expensive?

In the RAM model, you're allowed to do unbounded indirect access (pointers can be arbitrarily large and still fit in a single machine word). In the Bit Complexity model (no wiki article, sorry), ...
5
votes
1answer
72 views

How hard is this constrained $n$-rooks problem?

I asked this over on math.stackexchange.com, then I found out about this forum. Suppose you have an $(n\times n)$-chessboard, together with a constraining function $C : n \times n \to 2$ where ...
4
votes
2answers
338 views

Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

I'm a little stuck on this question, any help would be appreciated! Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is ...
3
votes
1answer
57 views

What happens to quantum algorithms such as BB84 if P=NP

Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible). The BB84 algorithm (http://en.wikipedia.org/wiki/BB84) is based on the idea that by ...
1
vote
1answer
28 views

Why is there only a polynomial number of provers in multi-prover interactive protocols?

The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following: There are provers $P_1, P_2, \dots, P_k$ in a multi-prover interactive proof system such ...
-2
votes
0answers
22 views

research on relations between density of languages and reductions

consider the "density" of a language $L$ roughly defined as the ratio of accepted words to total number of words eg something like $\rho(n)=f(n)/g(n)$ where $n$ is the word length. now consider ...
1
vote
1answer
36 views

A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

Wikipedia states on sparse languages that There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ ...
5
votes
1answer
48 views

Easy infinite subclass of cubic graphs for Hamiltonian cycle problem

I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs. I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle ...
1
vote
2answers
115 views

Does this mean $P = NP$

I am not a formally trained guy on Complexity theory, but due to interest I am learning it. Based on different feedbacks, I have started my journey with Micheal Sipser's "Theory of Computation" (2013 ...
4
votes
1answer
30 views

First Order interpretation of arbitrary structures as a graph

I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph". Given some arbitrary ...
45
votes
5answers
6k views

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either ...
2
votes
0answers
47 views

Are there online available solved homeworks on complexity theory?

I have never seen this subject before but certain things I read got me curious. I found various online lecture notes on complexity theory and theoretical CS but almost no where do I see solved ...
3
votes
3answers
74 views

number encoding effect on complexity

I started reading the book "Data Structures and Network Algorithms" by Robert Tarjan, which is a classic (but a bit outdated - 1983) and I am a bit perplexed by the paragraph in the first chapter, ...
11
votes
2answers
872 views

Is the “subset product” problem NP-complete?

The subset-sum problem is a classic NP-complete problem: Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ that sums to $k$? A student asked me if this variant ...
3
votes
1answer
57 views

Can quantified renamable Horn formulas be identified using the same procedure as unquantified formulas?

Definition: A renamable Horn formula is a Boolean formula that can be transformed into a Horn formula by flipping the polarity of every instance of one of more of its variables. Example: $\qquad ...
2
votes
1answer
63 views

Is FNP = FEXPTIME if and only if NP = EXPTIME?

It is very well known that if the classes $\sf FP$ and $\sf FNP$ are equal, then also the classes $\sf P$ and $\sf NP$ are equal (see e.g. FNP on Wikipedia). Is it also true that if $\sf ...
1
vote
3answers
136 views

Why is SAT in NP?

I know that CNF SAT is in NP (and also NP-complete), because SAT is in NP and NP-complete. But what I don't understand is why? Is there anyone that can explain this?
4
votes
1answer
179 views

Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

I am studying now for a test in my complexity course. When I solved previous exams I saw the following question: Prove that the language $L$ of all directed graphs on $n$ vertices that contain exactly ...
9
votes
1answer
285 views

What is complexity class $\oplus P^{\oplus P}$

What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing ...
3
votes
1answer
50 views

Why is $BPP$ closed under complement?

Why is $\text{BPP}=\text{co-BPP}$? I tried to find a proof online but couldn't. Can anyone please provide a quick explanation (if it's trivial and I just can't see it) or a link to a proof?
-3
votes
1answer
56 views

exponential lower bound on boolean formula conjunctions, what complexity class? [closed]

this new paper A Lower Bound for Boolean Satisfiability on Turing Machines by Hsieh asserts an exponential lower bound for a TM time complexity on a problem of finding whether a solution exists to a ...
2
votes
2answers
43 views

Computational complexity theory books [closed]

I recently attended a lecture on an introduction to computation complexity and I am looking to find out more, I haven't studied computer science or discrete mathmateics at university and I was ...
2
votes
2answers
133 views

Is the problem of evaluating a boolean formula on a given assignment P-complete?

I know that the CIRCUIT VALUE problem is P-complete. In the CIRCUIT VALUE problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given ...
2
votes
1answer
46 views

Computing the number of bits of a large power of integer

Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$? One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor ...
1
vote
0answers
56 views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
3
votes
2answers
97 views

Why does the NP completeness of the Hartree-Fock method not lead to difficulty in practical calculation?

I read Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory. In appendix, it is claimed that In the following, we show that approximating ...
-2
votes
0answers
39 views

What complexity does the set of all tautologies in predicate logic have?

If we assume $\mathsf{NP} \neq \mathsf{co\text{-}NP}$, is the set of all tautologies in predicate logic NP-complete, in NP but not NP-complete, co-NP-complete or co-NP but not co-NP-complete? I ...
10
votes
1answer
198 views

Use minimum number of swaps so each bin contains balls of the same color

There are $n$ bins, the $i$th bin contain $a_i$ balls. The balls has $n$ colors, there are $a_i$ balls of color $i$. Let $m=\sum_{i=1}^n a_i$. A swap is take a ball from one bin and swap with a ball ...
12
votes
1answer
148 views

NP-complete problems not “obviously” in NP

It occurred to many that in all the $\textbf{NP}$-completeness proofs I've read (that I can remember), it's always trivial to show that a problem is in $\textbf{NP}$, and showing that it is ...
-3
votes
1answer
39 views

Why is Mixed Quantified Horn SAT in PSPACE?

I want to prove that Mixed Quantified Horn SAT is a PSPACE-complete problem. I have proved that it is PSPACE-hard. How can I prove that it is in PSPACE? My study: To prove QSAT to be in PSPACE: ...
0
votes
1answer
27 views

Intersection and partial quantity decidability [closed]

I'm still insecure in the section decidability (no proof needed, I want to divine it): X is decidable and Y is undecidable. Is the intersection of X and Y decidable or undecidable? X is decidable ...
3
votes
2answers
105 views

Need Help Reducing Subset Sum to Show a Problem is NP-Complete

I want to show that the following problem is NP-Complete: For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such ...
8
votes
0answers
71 views

Would $\sf RP = NP$ imply $\sf NP = coNP$?

If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$? I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the ...
6
votes
1answer
66 views

Why doesn't a time cutoff convert NP problems into co-NP? [duplicate]

Suppose you have an NP problem, and a polynomial time verifier which accepts valid solutions within $f(n)$ operations. You make a tweak to the verifier program, so that if it takes more than $f(n)$ ...
6
votes
0answers
40 views

What do complexity classes look like, if we use Turing reductions?

For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions). This leads to pictures like this: (under standard conjectures). I'm sure we're all ...