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

2,943 questions
Filter by
Sorted by
Tagged with
0answers
4 views

### Complexity of Quadratic Programming where the negative eigenvalues are non-feasible directions

Dear Optimization Community, playing around with stuff for my thesis, I derived a quadratic problem in the general form \begin{equation} \begin{aligned} \min_{x} \quad & x^TQx + c^Tx \\ \textrm{s....
1answer
42 views

### Complexity of $Th(\langle \mathbb{N},= \rangle)$

I can prove that the decision problem of $Th(\langle \mathbb{N},= \rangle)$ is PSPACE-hard. However, the recursive algorithm to show it is in PSPACE would not work, since variables are unbounded and ...
1answer
59 views

1answer
25 views

### The Set Cover Problem, but instead of solving for when the Union of subsets of S is U, I want the union to be or contain a specific subset of U.

Summary I wonder if there is a solution to a simpler (or at least less strict) version of the Set Cover Problem where instead of searching for the smallest subset of $S$ whose union is equal $U$, I ...
0answers
17 views

### Simplification of time complexity notation

I want to simplify a big O time complexity notation for my algorithm. The algorithm calculates relative distances between a subset of sampled nodes Vs and all other nodes V in graph G through a single-...
0answers
20 views

### Using Rice's Theorem to prove undecidability of a language that contains all palindrome

I need help with this excercise about Rice´s Theorem. Using this language: P = {$\langle M\rangle \mid L(M)$ contains all palindromes} prove it is undecidable.
1answer
225 views

### Is there an explicitly known Diophantine equation whose solvability is undecidable in ZFC?

Reading the Wikipedia article on Diophantine sets, I was intrigued by the following remark near the end: Corresponding to any given consistent axiomatization of number theory, one can explicitly ...
1answer
45 views

### Proving that a greedy algorithm is an $\frac{1}{2}$-Approximation algorithm for the unbounded Knapsack problem

With the unbounded Knapsack problem we have $n$ objects $x_i$, with a value $v_i$ and weight $g_i$ for $i = 1,...,n$, as well as the total capacity of the knapsack $G$. We want to maximize the value ...
1answer
71 views

### Complexity of the pure theory of equality

The first-order pure theory of equality (Monk, Mathematical Logic, 240-242) has the equality predicate as its only (relation) symbol. Furthermore, I assume the convention in logic is that any ...
0answers
27 views

### solve $t(n)=2t(\frac{n}{4})+1$ using recursion tree method?

i have tries to many times but i could not conclude the answer. Anyone please help me to find the solution . Use Recursion tree method to solve it. Also provide all steps , that will help me to ...
1answer
30 views

### What would be the implications of NP=Co-NP?

The most famous open problem in Computer science is whether P = NP or not, but a less famous yet related problem is whether NP = Co-NP, now what kind of chaos could this cause if it was true? I ...
1answer
13 views

### Quantifying the complexity of the structure of a statistical model (or arbitrary program?)

I'm working with some folks to improve a benchmarking database for MCMC samplers. So there are canonical models, data, and posteriors. It would be useful to be able to automatically rank models ...
0answers
12 views

### What is the turing degree of different concrete problems? (looking for examples)

Despite there is a lot of information about the lattice of turing degrees, I have found very little information on the turing degree of a known uncomputable object, I'm looking for examples. This is ...
0answers
6 views

### Greatest totally unimodular submatrix

Let's say I have a $A_{m,n}$ dimensional matrix. Is there a fast way (P-time) to find the biggest i for which there is a $A_{i,i}$ TUM submatrix? (Easier version) Is there a fast way (P-time) to find ...
1answer
28 views

### How to compute the reciprocal of big O

Now I have the function $$f(k) = \frac{k}{M + k + O(\frac{1}{k-1})}, k\in\{2, 3, \cdots\},$$ where $M>1$ is a constant. So how to get the big O form of $f(k)$? I mean can I get the following ...
0answers
37 views

### categorical logic and computation

After encountering the field of Categorical Logic recently, and more specifically the nLab page on Computational Trilogy as well as this paper, I'm under the impression that we have a pretty complete ...
1answer
24 views

### Are primitive recursive functions computable in logarithmic space?

How can I prove that every primitive recursive function is computable on logarithmic space complex nondeterministic Turing machine? Any help will be much appreciated!!
1answer
55 views

### Build non-decreasing $f$,$g$ from $\Bbb N$ to $\Bbb N$ such that $f$ is not $O(g)$ and $g$ is not $O(f)$

Show that there exist non-decreasing $f,g:\Bbb N\to \Bbb N$ such that $f\neq O(g)$ and $g\neq O(f)$. ($\Bbb N$ is the set of strictly positive integers.) Source: Victor Shoup's "A computational ...
0answers
30 views

### Is there a combinatorial structure easy to count while difficult to sample?

In the theory of complexity, the counting problem is to compute the number of specified structures, e.g., count the triangles in a given graph. the sampling problem concerns how to generate uniformly ...
1answer
25 views

### Complexity of finding the cheapest path with length constraint

Given a directed Graph $G=(V,A)$ where $V$ is the set of vertices and $A$ is the set of arcs with corresponding positive costs $c_{i,j}$, find the cheapest path $p$ from a given vertex $s\in V$ to a ...
1answer
59 views

### Alphabetical complexity of algorithms.

I have posted elsewhere the following thought: For first order theories, is it correct that there is a brute force algorithm that tells us the shortest proof length for any given theorem ('length' ...
0answers
12 views

### How to deduce the computational complexity of eigendecomposition.

What is the computational complexity of eigendecomposition of a matrix, and how to prove? Let $L$ be, for example a $n \times n$ symmetric matrix and let \begin{equation} L= U\Lambda U^T \end{...
1answer
49 views

### Can there be a problem for which we can prove there's a polynomial time algorithm and can prove that can't prove an algorithm is such?

For a fiction story i imagined the following situation: there'd be a problem whose complexity depends on a natural number, for which a superpolynomial algorithm is known. Then a non-constructive proof ...
1answer
31 views

### To show that $a^n \in O(n!)$

$\forall n \in \mathbb{N} , a \in \mathbb{R} \wedge a > 0$ $$a^n \in O(n!)$$ I need to show it. Probably I should use the Induction but I am not sure, anyone has tips for me please?
1answer
29 views

### To prove or disprove mathematically $n \log_{3}{n^2} \in \Theta(n(\log_3 n)^2)$

I have to prove mathematically that $$n\log_{3}{n^2} \in \Theta(n(\log_3 n)^2)$$ and $$4^n\log_3n \in o(6^n)?$$ So anyone can at least give me a hint where to start? Which proof method should I use?
0answers
35 views

1answer
8 views

### Problem deriving b using the master theorem

Given the definition: $$T(n) = aT(n/b) + n^c$$ I am struggling to derive the value of $b$ from the following problem: $$T (n) = T (4n/5) + O(1)$$ I feel the value is $5/4$, but I am not sure why ...
0answers
80 views

0answers
9 views