Time complexity of decision problems or relations among time-bounded complexity classes. (Use [tag:analysis-of-algorithms] for the time taken by particular algorithms.)

learn more… | top users | synonyms

4
votes
1answer
51 views

Approximate matching in table of integer vectors

Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving. I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain ...
6
votes
2answers
171 views

P-complete decision problems about integers

Are there any known examples of P-complete decision problems which take as input a single integer? (non-unary, as unary feels like un-naturally forcing the issue) It feels like there are many ...
5
votes
1answer
140 views

Hierarchy theorem for NTIME intersect coNTIME?

$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap ...
3
votes
0answers
71 views

Complexity of eigenvaue problem

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices). What is the best time lower bound it is known? ...
11
votes
2answers
202 views

What is an equivalent definition of mP/poly in terms of a Turing machine?

P/poly is the class of decision problems solvable by a family of polynomial-size Boolean circuits. It can alternatively be defined as a polynomial-time Turing machine that receives an advice string ...
3
votes
2answers
167 views

Runtime of Tucker's algorithm for generating a Eulerian circuit

What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...
2
votes
0answers
107 views

Complexity of Knapsack-type problem with applications to computational workflows

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
9
votes
1answer
281 views

Simple path on dag with backward edges

What is the complexity of the following problem ($\in$ P? NP-hard?): Input: a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$. ...
-6
votes
1answer
144 views

Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
7
votes
2answers
320 views

Generalized Geography on graphs of bounded treewidth

Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play ...
1
vote
0answers
64 views

What is the minimal known space for polytime algorithms

Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured ...
8
votes
2answers
276 views

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

In the movie Inception Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource ...
4
votes
0answers
101 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

I already posted this question here but I didn't receive an answer, so I'm posting it here as well :) Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as ...
-2
votes
1answer
129 views

Algorithm to determine if given algorithm runs in polynomial time [duplicate]

In general, the undecidability of the halting problem prohibits the general determination of an algorithm's complexity. However, I can see no reason why the halting problem prohibits one from deciding ...
2
votes
0answers
78 views

number of iterations of this algorithm (upper bound)

Let $(A, dist)$ be a finite metric space. Consider the following "$p$-center problem": given a positive integer $p$, find a subset $B$of $A$ such that $|B| = p$ and which minimizes the number $\max_{a ...
3
votes
1answer
358 views

Is the following problem in P or in NP?

Given an integer $K$, a set of tasks $T=\{a_1,b_1,\dots,a_n,b_n\}$ with sequence dependent execution times $E:T \times T \rightarrow \mathbb{N}$ and precedence constraints on $T$ of the following ...
6
votes
1answer
80 views

Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
1
vote
0answers
44 views

Computational complexity of Initial Value Problems of ODEs

Are there known results on computational complexity of initial value problems of ODEs? As my question may be somewhat vague, I want to mention that I'm mainly interested for results on the ...
2
votes
0answers
87 views

Is the problem “Binary Sorted Min Sum” already known under an other name?

A computer scientist oriented toward applications gave me the following problem: Given a positive integer $n>0$, an increasing function function $f$ and a decreasing function $g$, both ...
8
votes
1answer
287 views

DFA intersection algorithm for special cases

I'm interested in efficient algorithms for DFA intersection for special cases. Namely, when the DFAs to intersect obey a certain structure and/or operates on limited alphabet. Is there any source ...
8
votes
0answers
64 views

Finding a median in a union of sets given as sorted arrays [duplicate]

You are given $k$ sorted arrays $A_1, A_2, ..., A_k$, each containing $n$ elements. How fast can you compute the median of $A_1 \cup A_2 \cup ... \cup A_k$ ? I have a solution running in ...
0
votes
1answer
186 views

Finding $x_1,x_2,…,x_k$ such that $n=x_1!+x_2!+…+x_k!$ and $k$ is minimal [closed]

Here is a problem I'm trying to solve: Given an integer $n$ return a list $[x_1,x_2,...,x_k]$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is as low as it can be. I'm thinking of creating a list of n ...
7
votes
0answers
445 views

Time complexity of a branching-and-bound algorithm

Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching ...
2
votes
0answers
176 views

Subset sum solver. Worth continue working on this method? [closed]

I have been working in a subset sum problem solver for some time. The implementation is an exact/exhaustive search solver. The variable determining the asymptomatic growth rate is just $N$ (the ...
5
votes
1answer
138 views

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why? Details: http://en.wikipedia.org/wiki/Powerset_construction states that the ...
6
votes
0answers
72 views

Complexity of solving vs verifying in P

Thinking of (seemingly) very different complexity of finding a solution to a NP problem and verifying it as the basis of practical cryptography, I am wondering if such separation is possible among ...
2
votes
0answers
93 views

Recent insights on algorithms for 1D bin packing

This is just a general question on recent algorithms for the 1D bin packing problem. I just want to collect some information on this issue, so I’m grateful for any information. Especially heuristics ...
4
votes
3answers
107 views

Fast high-dimensional K-nearest neighbors

I'm aware of this question http://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm But it's not the same question as I'm asking. Because, Octree and its generalization are only ...
6
votes
1answer
106 views

What's the complexity of recognizing equivalence for the following relation?

Consider the set $\mathcal{M}_{m,n}(\mathbb{Z})$ of $m$-by-$n$ matrices over, e.g., integers. We say that two matrices $A$, $B \in \mathcal{M}_{m,n}(\mathbb{Z})$ are equivalent if $A$ can be obtained ...
-2
votes
0answers
46 views

Little o Notation [closed]

I understand the little-oh notation a bit, but there is still some confusion. By definition, I get that f ∈ o(g) means that |f(x)/g(x)| approaches 0 as x approaches infinity. I also read somewhere ...
-1
votes
1answer
102 views

Using master theorem when there is a constant in the recursive term [closed]

Is it possible to use the master theorem to find the asymptotic growth of a function of the form: $$T(n) = aT(\frac{n}{b}+c)+f(n)$$ Where $c$ is a constant. Can we safely ignore this constant and use ...
6
votes
1answer
2k views

Magic constant to solve NP-complete problem in polynomial time

Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial ...
6
votes
2answers
349 views

Complexity of finding even cuts for a graph

Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in ...
7
votes
3answers
256 views

Total orders which are the transitive closure of a set in P

I am wondering if there is an example of the following form. It seems highly plausible that there should be but I am struggling to come up with one. Consider $T \subseteq \mathbb{N}^2$, a set ...
3
votes
0answers
36 views

Limits of parallel computing with local connections?

There are successes with an increasing numbers of individual computational units in GPUs or as processor cores. Given someone made the effort to build a huge array of processors which - however - can ...
2
votes
1answer
168 views

Max flow: either saturate an edge or avoids

Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half ...
-1
votes
1answer
192 views

Is the running time of Boyer-Moore linear?

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)? Are there any sublinear ...
2
votes
1answer
173 views

Time complexity of d-dimensional convex hull

Consider the convex hull problem in $\Re^d$: Input: a list of $n$ points $S$ in $\Re^d$, Output: the vertices of the convex hull of $S$. What is the best lower bound on the time complexity of ...
1
vote
0answers
135 views

proving speedup phenomenon does not apply to any open complexity class separations

Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question. the Blum speedup ...
12
votes
3answers
2k views

Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart. ...
1
vote
2answers
214 views

What is the asymptotic time complexity of the number of steps of “Half Or Triple Plus One” ( HOTPO)?

The "Half Or Triple Plus One" process goes as follows: start with $x=n$ for some value of $n$ if ($x$ is odd) $x = 3x+1$ else $x = \frac{x}{2}$ if ($x$ > 1) goto (2) ...
2
votes
1answer
100 views

Efficient Shamir secret sharing reconstruction

Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the ...
0
votes
1answer
179 views

maximum weighted 2D coverage problem by a rectangle

Let $P=\{p_1,\ldots,p_n\}$ be a set of $n$ points in a 2D plane, that is $p_i\in \mathbb{R}^2$, $\forall i=1,\ldots,n$. Each point, $p_i$, is associated with a weight, $w_i \geq 0$. Imagine a ...
13
votes
4answers
373 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
2
votes
1answer
126 views

Is there an additive time hierarchy theorem?

I would like something like this to be true: Conjecture: There is a function $g(n)$ such that for all functions $f(n)$ (perhaps satisfying some reasonable properties, like time-constructability), ...
4
votes
3answers
127 views

Remove unneeded atoms in CNF minimalization (SAT preprocessing)

This might be a very basic question. I am interested in all atoms of a propositional formula that can be removed from a particular formula, while the derived formula has the same satisfiability ...
4
votes
3answers
501 views

Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

An "algorithm" for calculating $ax+b$ would take the steps Calculate $a$ times $x$ Calculate $b$ plus the result of previous line. But if the values of $a$ and $b$ are known, can we create a more ...
8
votes
0answers
237 views

Linear space language that requires exponential time without ETH

The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$ requires ...
3
votes
1answer
145 views

Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers

It is often said that memoization brings the complexity of recursive-descent parsers from exponential to polynomial. However, I had a hard time finding an example grammar that triggers the exponential ...
1
vote
1answer
156 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...