Questions tagged [time-complexity]
Time complexity of decision problems or relations among time-bounded complexity classes. (Use [tag:analysis-of-algorithms] for the time taken by particular algorithms.)
293
questions
2
votes
1answer
79 views
Complexity of unbalanced bipartite isomorphism
For $i=1,2$, let $G_i=(A_i\cup B_i,E_i)$ be an undirected bipartite
graph with bipartition $A_i$ and $B_i$, where $|A_1|=|A_2|=a$ and
$|B_1|=|B_2|=b$ with $a\le b$.
Question. Is the problem of ...
1
vote
1answer
93 views
Induction on all polynomial runtimes?
Has there ever been a proof technique to show that a language isn't in $\mathrm{P}$, by showing inductively there isn't any $k$ for which the language is in $\mathrm{TIME}(n^k)$?
e.g.: $L\notin \...
0
votes
0answers
53 views
What is the run-time of LP?
Are there any further generalizations known to the result about run-time of a LP than what is stated in Theorem 1 of these lecture notes,
https://nisheethvishnoi.files.wordpress.com/2018/05/lecture71....
1
vote
1answer
68 views
Are there common names for the subtiers of PTIME?
We all know P, or PTIME, I think, as a common name for the class of polynomial-time problems. Are there common names for the first few levels inside P; that is, for constant-time, linear-time, ...
-5
votes
2answers
167 views
A sandwich Algorithm / Data Structure [closed]
$O(n^c)$ is asymptotically greater than $O(\log^d n) $ for all possible pair of values of $c$ and $d$.
Can you give an example of a problem (or data structure) which has running time (or query/...
-2
votes
1answer
148 views
Evidence integer multiplication is in linear time?
After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
0
votes
0answers
54 views
When can convex optimization be considered to be exactly solvable?
If one is trying to find the global minima of a convex function using gradient descent then one will get a run-time which is a function of $\epsilon >0$ where $\epsilon$ measures the accuracy of ...
18
votes
11answers
2k views
Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form?
I understand lots of things that might cause a log ...
5
votes
0answers
160 views
Complexity of extracting a coefficient of a polynomial in multiple variables
I'm looking for efficient algorithms for problems of the following type:
Let's say we have the variables $x_1,...,x_n$.
Over these variables, we are given a function $p_1\cdot ... \cdot p_m$, ...
10
votes
2answers
2k views
What is a natural problem in theory of computation?
In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]:
Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm.
My question ...
1
vote
0answers
96 views
How to prove a general convex set is nonempty or empty in polynomial time?
The general convex set should be represented by a set of (generalized) inequalities $f_{i}(x)\leq 0 $ with $ f_{i}(x) $ being convex in $ x $.
I know ellipsoid method and interior method, but I do ...
4
votes
1answer
130 views
Consequences/existence of problems without any “optimal” algorithm
Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S_P$ denote the set of algorithms $A_1, A_2, \dots$ which deterministically solve $P$. Based off ...
6
votes
0answers
183 views
Nondeterminstic Linear Time vs Other Complexity Classes
Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
-4
votes
1answer
55 views
what does NP ⊆ DTIME(…) mean?
Recently I've seen inside theory of a paper. This time complexity, DTIME, is completely new for me. Can somebody explain it?
Also, the paper shows that the misinformation containment problem cannot ...
4
votes
3answers
291 views
Is counting simple cycles in $P$ for graphs of bounded tree width?
Motivation:
Determining if a graph has a Hamiltonian cycle is $NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either ...
9
votes
1answer
325 views
Hidden Constants in Complexity of Algorithms
For many problems, the algorithm with the best asymptotic complexity has a very large constant factor that is hidden by big O notation. This occurs in matrix multiplication, integer multiplication (...
5
votes
0answers
262 views
Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?
Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in ...
2
votes
0answers
66 views
Cost of in-place partitioning integer arrays
Suppose we are given an array $a\colon[n]\to[m]$ of length $n$ (and each entry is between 1 and m). We will denote the $i$th entry of the array as $a[i]$.
Task: Permute the array $a$ in-place so that ...
3
votes
1answer
136 views
Given a subset of of the hypercube and an affine transform of it, find the affine map
This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some ...
7
votes
2answers
319 views
Given a subset of the hypercube and a copy translated by s, find s
Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
0
votes
0answers
58 views
Faster than linear set intersection
Is there a probabilistic data structure, such as the bloom filter, for which we could perform intersection superlinearly (at the cost of false positives)?
(I only know of a O(n) time complexity set ...
16
votes
2answers
1k views
“Almost sorting” integers in linear time
I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but ...
1
vote
0answers
31 views
Techniques to improve the efficiency of Dynamic Time Warping Algorithm
I am analyzing a set of time series that are shifted along the x-axis (see image below for clarification). I intend to average the time series and for that I would like to overlap all the start points ...
-1
votes
1answer
85 views
Why is $BPP^{NP}$ in polynomial hierarchy? [closed]
Why is $BPP^{NP}$ in the polynomial hierarchy?
I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. However, how does that imply $BPP^{NP}$ is inside the polynomial hierarchy?
7
votes
1answer
241 views
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
9
votes
1answer
567 views
2-NEXPTIME-complete problems
We have a problem and we found an algorithm that appear to be 2-nexptime.
I would like to find known 2-nexptime-complete problems in order to find a lower bound.
I found in literature mainly two ...
2
votes
0answers
52 views
Complexity of comparing extended integer power towers
Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
2
votes
0answers
82 views
Finding 3SUM witness when promised a solution
Suppose we have a 3SUM instance given with the promise that there exists at least one solution. Is the trivial $O(n^2)$ (modulo logarithmic improvements) solution still the best algorithm or is there ...
0
votes
0answers
43 views
Arranging sets in a hierarchy
Suppose you have sets $S_1, \dots S_m$ such that $\sum_i |S_i| = n$. The goal is to arrange all the sets into a (possible unconnected) DAG such that $S_i$ is a parent (or ancestor) of $S_j$ iff $S_j \...
2
votes
0answers
70 views
how is time complexity defined in computational learning theory
In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$.
Now ...
6
votes
1answer
238 views
Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)
In the wikipedia article on Time Complexity it is written that:
The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, ...
2
votes
0answers
39 views
Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q
As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
14
votes
4answers
2k views
Counting the number of vertex covers: when is it hard?
Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.
I'd like to know if there is any result showing how the hardness of such problem varies with ...
1
vote
0answers
95 views
Parallel building time of a k-d tree on n points with n processors
Given a point set with $n$ points to build a k-d tree on. We have $n$ processors available. What is the time-optimal building time for the k-d tree?
A straight forward parallelization would be as ...
2
votes
0answers
38 views
Minimize The Number of Connected Components in Hit-map of A Boolean Matrix
Suppose there is a matrix with the value of 0 and 1. The hit-map of the matrix (0 is blue and 1 is red) create some connected component (see the following figure as an instance):
Is there any ...
1
vote
0answers
20 views
Worst case polynomial in elimination theory under rank conditions?
Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree ...
18
votes
5answers
595 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 ...
6
votes
0answers
124 views
Evaluating addition chains
I hope this is a suitable place to ask this question.
An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
8
votes
1answer
219 views
How “hard” is it to maximize a polynomial function subject to linear constraints?
General Problem
Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
1
vote
0answers
275 views
EXPSPACE proof and its implications
I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below.
\begin{equation} \label{eq:nip_obj}
\min_{x \in \Phi} \sum_{i = 1}^n ...
9
votes
0answers
144 views
Time complexity of exponentiating s-sparse matrices
Could someone suggest me a reference which discusses the time complexity of algorithms meant for exponentiating (finding $e^A$ approximately given $A$) s-sparse matrices, along with their error rates?
...
10
votes
3answers
546 views
Equivalent formulation of complexity theory in Lambda Calculus?
In complexity theory the definition of time and space complexity both reference a universal Turing machine: resp. the number of steps before halting, and the number of cells on the tape touched.
...
3
votes
2answers
413 views
Is there a non-deterministic version of the complexity class PP?
From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)
Edit: Perhaps I ...
Emil Jeřábek supports Monica
10.9k3 gold badges40 silver badges64 bronze badges
3
votes
1answer
105 views
Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?
Does there exist an algorithm, about which a non-constructive $\omega$-consistent theory $A$ can prove that it has time complexity $O(f(n))$ where $n$ is some univariate function of the input, but ...
7
votes
1answer
215 views
TIME(n) versus TIME(nlogn)
The time hierarchy theorem implies TIME($n$) is strictly contained in TIME($n\log^{1+ε}n$) for all ε>0. Is the relationship between TIME($n$) and TIME($nlogn$) known?
2
votes
0answers
187 views
Complexity of solving a polynomial equation
Given a polynomial equation of degree n with m variables, that is guaranteed to have at least one solution, what is would be the ...
5
votes
0answers
110 views
Lower bound for enumerating k closest pair of points
Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ ...
16
votes
0answers
431 views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
4
votes
0answers
75 views
Finding a largest symmetrical subset of a k-CNF propositional formula
I have a k-CNF propositional formula $F$ which do not admit any global symmetry i.e. there is no permutation $\sigma$ of its variables such that $\sigma(F) = F$ . I'm interested in finding the largest ...
4
votes
1answer
103 views
Fast Finding Main Diagonal of Matrix Multiplication
Suppose we have two matrices $A_{m\times n}$ and $B_{m\times m}$. Such that $B$ is a symmetric positive definite matrix. Is it possible to compute main diganoal of $A^TBA$ in $O(n\times m)$?
