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.)

Filter by
Sorted by
Tagged with
-1
votes
0answers
22 views

Maximizing some type of inner product

For positive integers $n,m,k$, you're given a vector $c\in\mathbb{N}^n$ and a set $\Omega$ of $k$ finite non-empty sequences of numbers from $\{1,\dots,m\}$. You're asked to choose $\sigma_1\lt\...
-4
votes
0answers
30 views

Exponentiation: Function Problem that must take exponential time? [closed]

Introduction The powers of 2 seem to be a sparse language. Because every time I see a power of 2 expressed in a binary-string the amount of 0-bits is always equal to $X$ in $2^X$. For example, 10000 ...
-1
votes
0answers
26 views

Complexity of solving systems of linear equations with hash preimages

Consider the following problem: Let $H$ be an arbitrary cryptographic hash function. The goal is to solve the following system of linear equations with integer coefficients $$\boldsymbol A \...
1
vote
0answers
16 views

Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
1
vote
1answer
126 views

Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

Background It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$. Although some natural problems are known to exist, many of them ...
-1
votes
0answers
47 views

Fastest way for boolean matrix computations

I have a boolean matrix with 1.5 million rows and 20k columns, similar to this example: ...
2
votes
2answers
152 views

Problem in deterministic time $n^p$ and not lower

I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable). ...
6
votes
1answer
82 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 ...
-3
votes
0answers
48 views

Time compleixty of permutation [closed]

There are two approaches to compute all permutations of a string of unique characters: approach 1: building from permutations of first n-1 characters approach 2: Building from permutations of all n-1 ...
2
votes
0answers
181 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 ...
0
votes
0answers
54 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 ...
3
votes
1answer
107 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
98 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
57 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
69 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
176 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
153 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
55 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 ...
5
votes
0answers
162 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$, ...
11
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 ...
5
votes
1answer
134 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
186 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
79 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
0answers
270 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
67 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
138 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
324 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 ...
9
votes
1answer
349 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 (...
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 ...
1
vote
0answers
32 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 ...
4
votes
3answers
303 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
votes
1answer
89 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
252 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)?
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
73 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 ...
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 ...
6
votes
1answer
241 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, ...
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 ...
6
votes
0answers
126 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 ...
1
vote
0answers
277 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
148 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? ...
11
votes
3answers
573 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
416 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 ...
7
votes
1answer
216 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?
3
votes
1answer
106 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 ...

1 2 3 4 5 7