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.

Filter by
Sorted by
Tagged with
0
votes
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....
1
vote
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 ...
1
vote
1answer
59 views

Efficiency of paper and pencil division

I am trying to understand why the second paragraph under the stated division algorithm seems to mention the verification of one of the values for $q_i$ takes $O(l)$ time, while I think it would take $...
1
vote
0answers
12 views

Complexity of the sat problem for First Order Logic over an unbounded number of unary predicate and one equivalence relation

For this post, given a set $\tau_0$, a $\tau_0$-structure is a tuple $\mathfrak{S}=(S,(\overline{\sigma})_{\sigma\in\tau},\overline{R})$ where $S$ is a set, $\overline{\sigma}$ is a subset of $S$ and $...
0
votes
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 ...
0
votes
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-...
0
votes
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.
4
votes
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 ...
0
votes
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 ...
1
vote
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 ...
-1
votes
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 ...
2
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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!!
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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' ...
0
votes
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{...
4
votes
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 ...
0
votes
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?
0
votes
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?
0
votes
0answers
35 views

Optimal Transport Map for Gaussian

In the book "Computational Optimal Transport", the authors claim that the optimal transport map between two Multivariate Gaussian distributions $\mu$ and $\nu$ is given by: $$ T: x \mapsto ...
0
votes
0answers
33 views

Why check input x, $|x| \le\log n$ in the two proofs of Ladner's theorem?

Ladner's Theorem says that if $P \ne\ NP$, there exists intermediate complex class Language between P and NPC. in the proof, take the SAT as the NPC example. and the skill is proof by contradiction. ...
0
votes
0answers
25 views

computation of total complexity of an algorithm

Assume that I have a data sets witch consists of $n$ elements. Then, I apply two algorithms to this set, one after another, and each algorithm has time complexity $O(n^2\log{n})$. What is the oeverall ...
0
votes
0answers
21 views

Can we define n^k, when k < log(n) as the P problem upper limit?

In practice, we need define the character of P class precisely. Though in lots of paper, the index K less than log(n) is refered as very lower number. so my question is that if we can define the log(n)...
2
votes
0answers
40 views

Recurrence relation with non-constant coefficients and modular arithmetic

Let $a_n$ be a linear homogenous recurrence relation with constant coefficients. One can use the matrix form of the recurrence and then it is easy to determine $a_k$ mod $p$ for all $k$ and any prime $...
0
votes
0answers
35 views

Problem of finding shortest proof - some questions?

(1) Given a recursively axiomatizable theory with finitely many axioms, and with 'length of proof' defined as the sum of the lengths of the formulas that are the lines in the proof, is there an ...
1
vote
1answer
35 views

Is there a unit of measure for computational complexity; through quantum computers?

I'm concerned with trying to determine whether the same computational processes on a Turing computable algorithm can be ascertained for a quantum computer in some form of actual 'metric' for how many ...
0
votes
0answers
40 views

What is the complexity of this algorithm's formula?

I managed to determine the equation of my algorithm, which generates a graph and I tested it it works well, but I don't know how to determine the time and space complexity of it based on this formula: ...
2
votes
1answer
101 views

Problem of finding shortest proof - how complex is it? [closed]

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' means the sum of the lengths of the formulas that ...
0
votes
0answers
47 views

Can a theorem determine its own complexity?

Much how Gödel spoke of the Incompleteness Theorems, can a theorem determine its own complexity? Namely, I haven't seen a concise proof of the following that is not possible to determine in the ...
2
votes
2answers
76 views

Halving input but not at each step of a process

I am reading about an algorithm that takes as input $2$ integers and does the following to calculate the GCD: If both are even then then shift right (=division by $2$) both numbers and repeat If one ...
0
votes
0answers
49 views

Is there a way to indicate $NP^{\prod_i^P}$ or $coNP^{\prod_i^P}$ like in polynomial hierarchy?

In know that in polynomial hierarchy $\ \ \ \sum_{i+1}^P=NP^{\sum_i^P}$ $\ \ \ \prod_{i+1}^P=coNP^{\sum_i^P}$ I was wondering if there exists a way (and if it does make sense) to indicate $NP^{\...
1
vote
0answers
19 views

Understanding polynomial-growth condition

I'm reading Tom Leighton's 1996 paper: "Notes on Better Master Theorems for Divide-and-Conquer Recurrences". It contains a definition like this (I simplified slightly): We say that $g(x)$ ...
0
votes
0answers
15 views

Complexity of representing all satisfying assignments

I am not formally educated in Complexity Theory hence asking this question. In which complexity class should the problem of representing all satisfying assignments of a Boolean system (equivalently a ...
1
vote
2answers
51 views

Where does $\frac{x}{\log(x)}$ overtake $x^p$ for $0<p<1$?

I am teaching a mathematics for CS class, and one of the questions I put on the homework that nearly every student got wrong was if asymptotically the function $x^{.999}$ was less than $\frac{x}{\log(...
0
votes
0answers
9 views

What is Big-O time complexity of K-means++

I am try to find k-means++ time complexity.I red Arthur and Vassilvitskii's "k-means++: The advantages of careful seeding" paper. They said "O(logK)-competitive" but dont ...
0
votes
1answer
21 views

How come that I approximate a matrix by a product of less order matrices and I have more elements in the end?

I'm sure I'm missing something here but it's honestly giving me a headache. First of all, by the Singular Value Decomposition theorem I can decompose any $m \times n$ matrix into: $$A = \sum_{i=1}^k\...
0
votes
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 ...
0
votes
0answers
80 views

Show if the IS is NP-Complete

Let $G = (V, E)$ be an undirected graph. A subset $I \subseteq V$ of the vertices in $G$ is an independent set if no two vertices $u, v \in I$ are adjacent in $G$, i.e., for any $u, v \in I$, we have $...
0
votes
0answers
60 views

Complexity Theory: How can I prove if this have a witness finder

Given an NP language L, let a witness-finder for L be a polynomial-time algorithm M that actually outputs a yes-witness y for x whenever x ∈ L, but could behave arbitrarily if is not in L. (a) Show ...
0
votes
0answers
7 views
0
votes
0answers
8 views

Time Complexity of Ordinal Exponentiation (ordinals below $\epsilon_0$ in CNF)

Based on this question, I was thinking about the following: Suppose that we have finite alphabet $\Sigma=\{w,+,\times,exp,(,)\}$. Consider the set $A\subset \Sigma^*$ such that a finite string $s \in ...
0
votes
0answers
9 views

Covering the space below real polynomials by poly-logs

When dealing with runtimes of algorithms, the following question emerged in our group: Is every function $f(n)$, which has a sub-real-polynomial growth, bounded by $\log^k(n)$ for some $k \in \mathbb{...
1
vote
2answers
38 views

Properties of a digit sum and modulo

I am trying to solve a computational problem. The problem is like this; Let me define a number and show it as $s(n)$ that represents the smallest number, that has a digit sum of $n$. So $s(10) = 19 (1+...

1
2 3 4 5
59