Tagged Questions

Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

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
82 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
158 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
23 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
92 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 ...
1
vote
2answers
72 views

NP-hardness of an optimization problem with real value

I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$. ...
0
votes
1answer
58 views

tightest upper bound on binary search tree insertion? [closed]

The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that ...
5
votes
2answers
78 views

Exponential-size numbers in NP completeness reduction

In the proof of Theorem 4 in [GS'12], the authors reduce an instance of PARTITION to their problem. Therefore, they create for each element $a_i$ in the instance of PARTITION a number $2^{c \cdot ...
0
votes
2answers
71 views

Execution time of NP and NP-Complete algorithms

For P algorithms, we say that the execution time can be logarithmic O(log n), lineal O(n), quadratic O(n^2), etc. For NP and NP-Complete algorithms is there a way to represent the execution time? Or ...
0
votes
1answer
71 views

Problem with my proof that NP = coNP?

Is there a problem with this proof that NP = coNP? It suffices to show that Satisfiability can be solved efficiently with at most a polynomial number of queries to an oracle for Tautology. The ...
0
votes
2answers
94 views

Why does binary search take $O(\log n)$ time?

My question seems like an elementary question, but it's really not. Suppose I have one million cars in a line sorted in alphabetical order by license plate. I am standing at the top of the line with ...
7
votes
1answer
156 views

Is this classic puzzle book game NP-complete?

There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked ...
0
votes
1answer
43 views

Connection of “modern” runtimes and number of steps on a Turing machine

Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is ...
0
votes
1answer
33 views

Descriptive complexity: 3-colorability example

So in Neil Immerman's book http://books.google.co.kr/books?id=kWSZ0OWnupkC&pg=PA113&lpg=PA113#v=onepage&q&f=false, 3-colorability problem in descriptive complexity fashion is expressed ...
0
votes
3answers
39 views

A graph in descriptive complexity - is $x$ already a vertex?

So suppose that there is an undirected graph with edge connections known. Now in first-order logic there is quantifier $\forall x$. Then does this automatically refer to vertexes, or can we use ...
2
votes
1answer
77 views

Proof technique in complexity theory

I have a (stupid ?) question about complexity theory. It's about a "proof technique". I want to compare 2 models of computation. I want to prove that for each langage recognized in polynomial time by ...
1
vote
1answer
68 views

Reduction to Maximum Independent Set

Suppose you had a set $P$ of people. Every person $p_j \in P$ is familiar with atleast one other person $p_i$ (familiarity is symmetric). Is there a subset $S$ of people such that for $|S| \ge k$, no ...
-1
votes
1answer
63 views

are there any decidable problems not verifiable in polynomial time?

As I understand it NP requires a solution to be verifiable in polynomial time. Can you provide examples of solvable problems not verifiable in polynomial time ?
3
votes
1answer
129 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 ...
2
votes
1answer
76 views

Is FACTORIZATION or PRIMES known to be in LOGSPACE

Are the integer factorization and PRIMES known to be in LOGSPACE? Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known ...
2
votes
1answer
44 views

Poly-time computability of inversion of poly-time real functions

At pp. 7-8 of Ker-I Ko's Computational Complexity of Real Functions (1991), the following is stated for one dimensional cases: Let $INV_1$ be the operator that maps a one-to-one function ...
4
votes
1answer
78 views

Universal One-Way Functions

The Berman-Hartmanis conjecture discusses one-way functions (functions with hard to compute inverse functions). As a step to solving the conjecture, if one-way functions could be reduced to a ...
1
vote
1answer
60 views

Name for class of algorithms preserving accuracy/confidence

I am considering the following class of algorithms: The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input. The answer of procedure $f$ (we may assume it is ...
-2
votes
1answer
34 views

Why does reduction from vertex cover to subset sum use base-4? [closed]

Why does reduction from vertex cover to subset sum use base-4? 30.13 Subset Sum (from Vertex Cover)
2
votes
1answer
50 views

Is there a limit on the length of queries for the oracle?

Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My ...
4
votes
1answer
130 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$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
5
votes
0answers
38 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 ...
11
votes
2answers
95 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$)?
7
votes
4answers
221 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 ...
2
votes
1answer
67 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 ...
0
votes
1answer
25 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 ...
1
vote
1answer
52 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 ...
9
votes
1answer
114 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
62 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
30 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
82 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 ...
3
votes
1answer
62 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
29 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 ...
1
vote
1answer
39 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
66 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 ...
2
votes
2answers
138 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
36 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 ...
7
votes
2answers
157 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 ...
2
votes
0answers
54 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 ...
2
votes
1answer
70 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 ...
3
votes
1answer
61 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 ...