Questions tagged [computational-complexity]
Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.
3,577 questions
-3
votes
0
answers
62
views
Is it valid to compare solving vs checking NP problems using average time per logical step?
I’ve been exploring a measurement approach for NP and NP-complete problems based on average time per logical step.
I define:
...
0
votes
0
answers
37
views
Is Exact Matching with more than two colours NP-hard?
I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...
- 353
1
vote
1
answer
117
views
Complexity of $Th(\langle \mathbb{Z}; + , 1 \rangle)$ same as $Th(\langle \mathbb{Z}; + \rangle)$?
I want to know a lower bound for the complexity of the decision problem for $\langle \mathbb{Z}; + \rangle$. The below paper notes that Presburger arithmetic, originally $\langle \mathbb{N}; +\rangle$,...
- 287
2
votes
0
answers
23
views
Does the Interior Point Method Solve Klee-Minty Cubes adversarial instances in Polynomial Time?
I am a network engineer currently studying optimization problems. Out of curiosity, I was fascinated by the fact that the Simplex Method has an exponential worst-case complexity, a property famously ...
0
votes
0
answers
38
views
Is vertex enumeration preferable to the simplex method in linear programming for finding all basic feasible solutions?
Context
I'm studying linear programming and trying to understand when different solution methods are most appropriate.
I understand that the simplex method is generally better than vertex enumeration ...
- 83
5
votes
2
answers
641
views
Proof that NP is a subset of EXP
I would like to clarify a misunderstanding I have about the proof that all NP problems can be solved in exponential time. The argument as I understand it is that you can simply test all possible ...
- 319
1
vote
0
answers
110
views
Where is the relativized uniform complementor on r.e. indices stated explicitly (index-operator form)—existence for $\emptyset'$ and any minimality?
Let $\langle W_e : e\in\mathbb{N}\rangle$ be the standard effective enumeration of recursively enumerable (r.e.) sets, where
$$
n\in W_e \;\Longleftrightarrow\; \exists s\;\big(\varphi_e(n)\ \text{...
- 31
0
votes
1
answer
46
views
Prove Big Theta for degree p polynomial
Goal
Prove that $f(n) = a_pn^p + a_{p-1}n^{p-1} + ... + a_1n + a_0$ is $\Theta(n^p)$
Issue
I am having trouble proving $f(n)$ is $\Omega(n^p)$. I know I need a $c_0$ and $k$ such that $f(n) \ge c_0n^p$...
- 35
3
votes
2
answers
182
views
Solving a general 1st order ODE with a series expansion
I am interested in solving the general Cauchy problem:
$$\begin{cases}\frac{dx}{dt}=f(x, t) \\ x(t_0)=x_0\end{cases}$$
computationally. Of course, I know there are plenty of well-established methods ...
- 241
6
votes
0
answers
294
views
How does this algorithm "rank" amongst other in the literature?
By merging together the contributions from: a) this answer, b) the comments under this answer, we come up to the following:
Claim. For $n\in\mathbb N$, let $Q=(\{1,\dots,n\},*)$ be a quasigroup. Then, ...
- 5,601
4
votes
1
answer
222
views
Subgroup test runtime
In case of a finite subset of a group, the subgroup test boils down to showing that the subset is closed under the group operation. This holds, in particular, for the subsets of a finite group.
Q. ...
- 5,601
1
vote
0
answers
52
views
Prove that the zig-zag product of $G$ and $H$ (where $H$ is the smaller of the two) lifts $H^2$
Prove that the zig-zag product of $G$ and $H$ (where $H$ is the smaller of the two) lifts $H^2$.
I was reading Expander Graphs and their Applications (Lecture notes for a course by Nati Linial and ...
- 1,811
2
votes
0
answers
181
views
Transitivity check runtime
A necessary condition for a subset $\Sigma\subseteq S_n$ to be a transitive permutation group of order $n$, is to be... transitive. Is the best algorithm to check $\Sigma$'s transitivity faster than ...
- 5,601
2
votes
1
answer
99
views
Polynomial-Time Algorithms for Canonical Form of Ternary Matrices under Row/Column Permutations and Column Negations
We study equivalence classes of ternary matrices of size $m\times n$, where equivalence is defined via row permutations, column permutations, and negation of entire columns. Our goal is to define and ...
- 1,860
0
votes
0
answers
53
views
Can Nested tuples error calculation be improved by using complex numbers?
Hi I am trying to improve my error function . I have some data that is in form of nested tuple. These tuple nesting is base on importance of the data (all the lowest depth data is in as real numbers).
...
- 19