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.)
408
questions
5
votes
2
answers
230
views
What are the computations model with a constant slowdown ? (and why do we care about Turing machines)
One problem with Turing machines is that the universal Turing machine $U$ can simulate any machine $M$ but with a $\log$ slowdown, meaning $U(\#M,x)$ runs in time $O(T(n)log(n) + O(n))$, where $n=|\#M|...
- 301
7
votes
1
answer
241
views
Is parity of GI easy?
Given graphs $G,H$ let $N(G,H)$ be the number of isomorphisms between them. Is there polynomial time algorithm to compute $N(G,H)\bmod 2^t$ for every fixed $t\geq1$?
- 13.1k
1
vote
0
answers
159
views
Is finding the best permutation an NP-Complete problem?
We have a matrix $M$ of size $n$ by $n$ where
$M[i][j] \ge 0$ and $M[i][i] = 0$.
We want to create a permutation of integers $[1,\dots,N]$, like $\langle P_1, P_2,\dots,P_n \rangle$, such that
$$
\...
- 544
0
votes
0
answers
34
views
Possibility to Use Radix Sort for Linear Sorting of Floating Point Numbers?
Radix sort is a sorting algorithm that runs in linear time because it doesn't use algebraic comparisons. Its main limitation is that, because of this, it can only sort integers. However, a 32-bit ...
- 1
5
votes
3
answers
212
views
Why is order/choice an issue for a logic for PTIME
As I'm reading on the question of a logic for PTIME and in particular about CPT and its variants, whilst things make sense and I follow along, I came to realise that I don't fundamentally understand ...
- 51
0
votes
0
answers
58
views
Why can't we just reduce from Bounded HALT to Bounded PCP?
We know that:
PCP is famously undecidable (as it can encode any DTM), but
Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and
Bounded-PCP (there is a matching ...
- 101
-1
votes
1
answer
89
views
The role of Turing machines in computational complexity [closed]
In the popular book "Introduction to algorithms" by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead ...
- 99
-1
votes
1
answer
192
views
Calculation on Sparsification and critical clauses in SAT
I followed from this question.
I need to prove, the final result $s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$
But before prove the final result first I need to prove the $s_k \leq (1 − d/k))s_{\infty}$.
...
- 109
3
votes
1
answer
395
views
Time complexity of PPZ algorithm
I am trying to understand PPZ (Paturi, Pudlák, Zane) derandomization algorithm for k-SAT, it seems to be very difficult for me. The last line in the below of the image, I don't understand the time ...
- 133
7
votes
0
answers
115
views
Parameterized complexity of factoring
When multiplying integer numbers $A$ and $B$, one can use a 0-1 matrix to represent one of the multiplication steps. For example, given numbers (written in binary) $A=1101$ and $B=1011$ the matrix is:
...
- 355
0
votes
0
answers
50
views
Computational complexity of LambdaMART
Could someone provide a general estimate of the average (time) complexity of the LambdaMART learning-to-rank algorithm?
A particular implementation of LambdaMART is known as XGBRanker. It uses ...
- 1
1
vote
1
answer
86
views
Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs
I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
- 21
0
votes
0
answers
120
views
Complexity of, given any elementary function $f$ and a natural $n$, compute $n$ digits of $f(x)$
We define problem $A$ as follows. Each instance of the problem consists of:
(a) some succinct codification of an elementary function, that is, a function constructed by composing arithmetic operators, ...
- 408
2
votes
1
answer
109
views
Maximum cardinality disjoint cycle cover in undirected graphs
I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
- 828
3
votes
0
answers
92
views
What's the complexity of the "decision version" of counting the paths in a graph?
I learned that "counting the simple paths in a graph(whether directed or not)" is #P-Complete.
I'm wondering what the complexity is for its decision version.
Here are two types I'm ...
- 31