Questions tagged [time-complexity]
Time complexity of decision problems or relations among time-bounded complexity classes. (Use the [analysis-of-algorithms] tag for the time taken by particular algorithms.)
395
questions
8
votes
1
answer
367
views
Determining if a word of specific length exists that is not accepted by a NFA
It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard?
Given an NFA and a ...
- 113
1
vote
0
answers
234
views
Fast algorithms for evaluating functions with high Kolmogorov complexity
Motivation:
I am motivated by a concrete example that occurs in neuroscience, dendritic computation, which may be approximated by functions computable on binary trees [1]. To be more precise, I ...
- 311
0
votes
0
answers
250
views
Complexity of multi-objective optimization problems
How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?
It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
- 185
3
votes
1
answer
139
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 ...
- 539
1
vote
1
answer
108
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 \...
- 219
2
votes
1
answer
108
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, ...
- 271
-4
votes
2
answers
227
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/...
- 137
-1
votes
1
answer
233
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-...
- 12.8k
0
votes
0
answers
80
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 ...
- 1,443
5
votes
0
answers
171
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$, ...
- 151
14
votes
3
answers
3k
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 ...
- 143
2
votes
0
answers
113
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 ...
- 31
5
votes
1
answer
147
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 ...
- 603
6
votes
0
answers
237
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
1
answer
468
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 ...
5
votes
0
answers
318
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 ...
- 51
2
votes
0
answers
99
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 ...
- 173
4
votes
1
answer
162
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 ...
- 173
7
votes
2
answers
356
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 ...
- 173
11
votes
1
answer
833
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 (...
- 776
2
votes
0
answers
40
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 ...
- 21
5
votes
3
answers
466
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 ...
- 1,439
-1
votes
1
answer
170
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?
- 101
8
votes
1
answer
315
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)?
- 91
2
votes
0
answers
71
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 ...
- 643
2
votes
0
answers
94
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 ...
- 1,177
0
votes
0
answers
47
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 \...
- 1,177
2
votes
0
answers
104
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 ...
- 21
3
votes
0
answers
43
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 ...
- 131
7
votes
1
answer
272
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,037
1
vote
0
answers
101
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 ...
- 111
2
votes
0
answers
45
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 ...
- 189
1
vote
0
answers
26
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 ...
- 12.8k
6
votes
0
answers
138
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 ...
- 161
1
vote
0
answers
325
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 ...
- 185
9
votes
0
answers
159
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?
...
- 307
11
votes
3
answers
1k
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
2
answers
476
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 ...
- 383
7
votes
1
answer
310
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?
- 173
3
votes
1
answer
136
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 ...
- 900
2
votes
0
answers
954
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 ...
7
votes
1
answer
178
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$ ...
- 1,177
15
votes
0
answers
486
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 ...
- 2,537
3
votes
0
answers
95
views
Lower bound for reversing a list using queues
How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues?
Each queue is FIFO. Time refers to the number of operations on the queues.
...
- 2,537
4
votes
0
answers
83
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 ...
- 311
5
votes
2
answers
643
views
Data structure to determine if sets are disjoint in o(n) time
My initial question was exactly the title of this post, but after feedback from commenters I have formulated a more precise version of the question that attempts to capture its essence.
Does there ...
- 159
1
vote
1
answer
82
views
Can we replace deterministic part of alternative turing machine with some other equivalent machines?
I'm sorry if it is a low level question but I am so confusing.
If $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$ then $DTime(n) \subseteq \Sigma_2DTime(n^{0.2})$
Is this true that $\Sigma_2DTime(n^{0.2})...
- 23
-5
votes
1
answer
127
views
What do you think of Bokov's "CNF-SAT is in P" proof? [closed]
There are now several versions of G. V. Bokov's paper "Complexity of the CNF-satisfiability problem", cf. https://arxiv.org/abs/1804.02478
In the most recent version of his paper, the proof is only ...
11
votes
1
answer
551
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 ...
- 576
2
votes
0
answers
67
views
Bit complexity of factoring univariate polynomial over $\mathbb{Q}$ (rationals)
What is the bit complexity of finding all the irreducible factors $f_1, ..., f_r$ of a degree-$d$ polynomial $f(x) = \sum_{i=0}^d a_i\cdot x^i \in \mathbb{Q}[x]$ whose all coefficients are $B$-bit ...
