Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

0
votes
0answers
14 views

Draw out TM where 1<=n<=|w| the nth character from the left is equal to the nth character from right

We need to write TM for strings over {a,b,c} for some n, 1<=n<=|w| the nth character from the left is equal to the nth character from right. Can someone help me understand the meaning and how ...
3
votes
2answers
206 views

complexity of determining whether a language given by context free grammar is empty

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...
3
votes
1answer
45 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$.
6
votes
3answers
158 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 ...
1
vote
0answers
55 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 ...
0
votes
0answers
45 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
36 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 ...
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 ...
3
votes
2answers
109 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 ...
6
votes
2answers
264 views

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 ...
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
71 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} ...
1
vote
1answer
59 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 ...
3
votes
0answers
203 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 ...
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 ...
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 ...
8
votes
1answer
149 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 ...
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
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: ...
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
435 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?
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 ...
-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 ...
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 ...
1
vote
1answer
53 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 ...
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 ...
1
vote
1answer
146 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 ...
1
vote
1answer
29 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 ...
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 ...
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 ...
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 ...
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?) ...
-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 ...
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 ...
2
votes
2answers
102 views

Known lower bounds on halting for finite machines?

It's possible to determine whether a deterministic machine with finite memory will halt in O(n) time if the machine has n possible states. You simply run the machine until it halts or visits the same ...
7
votes
2answers
191 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$ ...
5
votes
2answers
204 views

Direct NP-Complete proofs

I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are ...
6
votes
0answers
81 views

Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine. Is ...
2
votes
1answer
97 views

Is finding a solution of a satisfiability problem harder than deciding satisfiability?

Is the problem of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression? In other words, is there another ...
5
votes
1answer
85 views

Complexity of Pythagorean triples

We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit ...
5
votes
1answer
157 views

Why does the solution of an NP problem have to be polynomial size?

I've read in "Introduction to Algorithms" (CLRS) that formal language $L$ is NP-language if and only if there is a polynomial verification algorithm $A(x, y)$ and a constant $c$ such that ...
4
votes
1answer
22 views

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...
4
votes
1answer
88 views

Complexity of Linear Diophantine equations

My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are ...