Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

3
votes
2answers
75 views

What problem cannot be solved by a short program?

BACKGROUND: Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of ...
3
votes
1answer
33 views

What if $NP\subseteq BPP$?

I'm new to complexity and came upon the following exercise which I'm unable to solve. Prove that if $NP\subseteq BPP$ then $\Sigma_2^p=\Pi_4 ^p$.
1
vote
0answers
48 views

Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
3
votes
1answer
70 views

Lower space bound on a turing machine accepting palindromes

Let $$ PAL = \lbrace x \in \lbrace 0, 1, \# \rbrace^* | x = rev(x) \rbrace $$ How do I show that a turing machine deciding $PAL$ must use space $\Omega(\log n)$? I have a feeling that I need to use ...
6
votes
2answers
246 views
+50

Proving NP-hardness of strange graph partition problem

I am trying to show the following problem is NP-hard. Inputs: Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph Output: Partition of $G$, $G_p=(V,E_p)$ obtained ...
3
votes
3answers
274 views

Good text on algorithm complexity

Where should I look for a good introductory text in algorithm complexity? So far, I have had an Algorithms class, and several language classes, but nothing with a theoretical backbone. I get the whole ...
17
votes
2answers
215 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 ...
0
votes
0answers
44 views

Is there a poly time algorithm for finding all approximate zeros contained in $[0,1]$ of a continuous poly computable $f(x)$ with at most m zeros?

Specifically we know that for our function $f$ ($f$ takes real values), $\infty>f(0)>0$, while $-\infty<f(1)<0$. So the classical binary search will find an approximate zero within ...
2
votes
0answers
35 views

Does $C$-complete = co-$C$-complete imply that $C$ = co-$C$? [closed]

Lets have an arbitrary complexity class $C$. Does $C$-complete = co-$C$-complete imply that $C$ = co-$C$? I think that the answer is yes, but I am not sure whether my reasoning is correct. I tried ...
3
votes
2answers
108 views

Word tiling, where you must use each tile exactly once

Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of ...
0
votes
0answers
30 views

How to proof co-C-completeness?

I have a problem $L$ which is in $C$-complete, where $C$ is a complexity class ($P, NP$ or any other). I have to proof that its complement $\bar{L}$ is in co-$C$-complete. I would like a little help ...
1
vote
0answers
79 views

Are rational functions with positive integer coefficients honest?

For every rational function $p(x)/q(x)$ where $p$ and $q$ are polynomials with non-negative integer coefficients, does there exist a polynomial function $h$, such that, if you input a reduced fraction ...
1
vote
1answer
70 views

Proving NP hardness of maximum sum of means of a partition into k sets

I am trying to show the following problem is NP-hard and would like some help. Inputs: Integer $k$, and unordered set of $N$ numbers, $O$ Output: the $\max \sum\limits_{S_i \in S} ...
3
votes
0answers
201 views

Showing that the language of graphs and nodes on an odd cycle is in NL

Let L be the language containing all the pairs (G,v) where G is a directed graph and v is a vertex in G such that G contains a cycle that contains v and the number of different vertices that appear ...
1
vote
1answer
58 views

Prerequisites of computational complexity theory

what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical ...
7
votes
4answers
2k views

Flaw in my NP = CoNP Proof?

I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out? Let A be some problem in NP, and let M be the ...
4
votes
1answer
54 views

Extracting maximum information from a set of exam answers and their scores

Imagine we have a multiple-choice exam with N questions. Suppose we have a set of K answer sheets to the exam and their total scores (1 for a correct answer on a question, 0 for incorrect). How much ...
0
votes
2answers
45 views

NP-hard proof with reduction from two known NP-hard problems

As I understand, to show that a certain problem P is NP-hard we can reduce a known NP-hard problem, Q, to problem in P in polynomial time. To show that the problem P is NP-hard in strong sense, we can ...
8
votes
1answer
148 views

Are all known algorithms for solving NP-complete problems constructive?

Are there any known algorithms that correctly output "yes" to an NP-complete problem without implicitly generating a certificate? I understand that it is straightforward to turn a satisfiability ...
4
votes
1answer
45 views

Computational complexity for more general problems

When I read computational complexity I encounter problems like 3-SAT, set cover, knapsack. In the first two variables are discrete. In knapsack the weights and values are integer and all three ...
4
votes
1answer
71 views

Decide whether there exists a walk of weight exactly k

Consider the following problem: Input: a directed graph $G = (V,E,\omega)$ where $\omega : E \longrightarrow \mathbb{Z}$, two vertices $v_1, v_2 \in V$, and a weight $k \in \mathbb{Z}$ Question: ...
0
votes
0answers
16 views

Physically implement Post BQP

Why is it not possible to physically implement post selection in quantum computing? If there were a means to implement it we could solve all PP problems in polynomial time since PP = PostBQP
3
votes
1answer
122 views

How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?

I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1). (a) Describe an algorithm that sorts an input ...
3
votes
1answer
53 views

The buckets of water problem

Let's consider the following problem (buckets/pails of water problem) (This problem may be known with different name. If does, please correct me). Let $B=\{b_1,...,b_n\}$ be a set of $n$ buckets. ...
3
votes
4answers
433 views

How can an algorithm have exponential space complexity but polynomial time complexity?

For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback ...
2
votes
1answer
32 views

Proof of P-Hardness by reduction

I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?
5
votes
2answers
480 views

Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes). The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s ...
3
votes
0answers
56 views

Problems that provably require quadratic time

I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$. The problem needs to have the following properties: $\Omega(n^2)$ runtime proof for any algorithm - ...
8
votes
1answer
86 views

What is the name of the problem? (partitioning graph into three covers)

I was wondering if this problem has a name: Given a simple graph whose edges are colored red, blue and green, $G=(V,B\cup R\cup G)$, is there a vertex-coloring $c:V\to \{B,R,G\}$ such that every edge ...
7
votes
1answer
102 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 ...
-2
votes
0answers
57 views

Show that the language of words that polynomially bound accepting inputs of a TM is in NP

I am doing the exercise 2.1 in the book "Computational Complexity: A modern approach" by Sanjeev Arora and Boaz Barak. Prove that allowing the certificate to be of size at most $p(|x|)$ (rather ...
0
votes
0answers
12 views

When proving a problem is NP-C, how do I select another NP-C problem for the transformation? [duplicate]

I'm taking an algorithms course in which we are discussing proofs that problems are NP-Complete. Our proofs usually take the form: Given a problem $\Pi$, 1. Prove that $\Pi$ is NP. 2. Select an ...
8
votes
1answer
106 views

Are regex crosswords NP-hard?

I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was. Can you solve the following problem in polynomial time or is ...
6
votes
0answers
48 views

Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
7
votes
2answers
190 views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ ...
0
votes
1answer
24 views

Polynomial time optimisation algorithm for a poly-time computable function with bounded number of maxima?

Suppose we have a polynomial time algorithm for computing a function (we think of as existing on rational numbers between $0$ and $1$ of limited binary length n). We know that this function is made up ...
1
vote
1answer
52 views

Is an algorithm in pseudocode a reasonable way to establish complexity?

We define the language $$ L = \{a^nb^n : n\geq0 \} $$ and we want to prove the following $$ L = \mathrm{DSPACE}(\log n)\,. $$ So we have to prove that by using $\log n$ space on the work tape of ...
2
votes
2answers
102 views

Finding an exactly weighted st-path in a digraph

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
1
vote
1answer
143 views

Is finding if a graph has k isolated nodes a NP-Complete problem?

I was wondering if finding if a graph has k or more isolated nodes is a NP-Complete problem. I found the following problem: Prove that the following problem is NP-Complete. Given a set of T ...
0
votes
0answers
45 views

Do poly-computable differentiable functions on [0,1] with bounded number of turning points have poly-time computable inverse?

Given a polynomially computable continuous function which is a composite of m strictly monotone functions, can we guarantee the existence of polynomially computable inverse? The function I have in ...
-1
votes
1answer
38 views

Relationship between an NP-hard problems with the subsets of them (part 2)? [duplicate]

I asked two questions about NP-hard problems here Relationship between an NP-hard problems with the subsets of them? and here Does this manner of proof for being NP-hard is true? but unfortunately ...
0
votes
1answer
87 views

NP-hardness proof, what is wrong with it?

My question is the following: If we have a problem divided into two versions, weighted and unweighted. Can we prove that the unweighted problem is NP-hard from the fact that the weighted problem is ...
4
votes
1answer
44 views

Understanding the Sipser-Gacs-Lautemann theorem

The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input. The class $\Sigma^p_2$ contains all ...
1
vote
1answer
48 views

What do we know about covering the edges of a graph by disjoint paths?

Two related things I have heard/know of are, (1) That there exists a polynomial algorithm to find a cover of the vertices by $k$ vertex disjoint cycles. (Can someone give a reference for this?) ...
6
votes
0answers
88 views

Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
8
votes
1answer
74 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 ...
10
votes
3answers
680 views

Decision problems in $\mathsf{P}$ without fast algorithms

What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known ...
12
votes
2answers
260 views

Does every NP problem have a poly-sized ILP formulation?

Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
-1
votes
1answer
38 views

How to reduce bin-packing problems? [duplicate]

This is my first time with reductions and I can't figure out how to do them. I have read the few standard examples that are given in the standard books. For example, given $n$ numbers $\{ 0 < ...
0
votes
0answers
56 views

Homomorphism erasing information

I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed. I got stuck in proving that, if P is closed under ...