Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

0
votes
0answers
17 views

Reduction of halting problem

I can show that this reduction !H ≤ H where H is the general halting problem an !H is the complement of it. But what with H ≤ !H ...
0
votes
0answers
12 views

Where are PPAD problems located?

I'd like to produce a figure like this one and I'd like to add the PPAD class and the PPAD-complete class. I know that those classes are somewhere inside NP-complete set, is this right? Could ...
4
votes
1answer
24 views

Is anything nontrivial known about quotients of complexity classes?

This question is just for fun and this is completely outside my area, so it's likely dumb; apologies in advance. By a "quotient" I mean the following: suppose you have two complexity classes, $A ...
0
votes
1answer
19 views

BigOh - How to determine the upper bound dealing with eccentric series?

I would like to know what is the way to determine the upper bound of a series in BigOh terms. For example, suppose the following series is given: 2 + 6 + 10 + 14 + ..... + ((4 * n) - 2) How can I ...
0
votes
1answer
58 views

How to prove $n^2$ is not in $n^3$

How would I go about to prove the simple complexity of $n^2$ is not in O($n^3$)? Also , how would I go about doing this for big Omega and Theta? Ex. Prove $n^4$ is not in Omega(n^3)??
2
votes
1answer
66 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...
-5
votes
3answers
72 views

Big O notations and asymtotic analysis [closed]

Kindly answer and explain it to me too. this is how i solved
1
vote
1answer
84 views

Efficient Verification for Travelling Salesman Problem

Through reading popular mathematical literature, I have learned the following two facts about computational complexity theory: The complexity class NP is the set of problems for which a candidate ...
0
votes
2answers
134 views

The result of O(f(n)) - O(f(n))

My question is in the field of the big-O-notation and complexity/asymptotic functions: Probably something that I'm missing, but I've couldn't find any well explained solution for the following: What ...
0
votes
1answer
51 views

Why can you find a $k$-clique in polynomial time, but determining if there is a $k$-clique is NP-complete?

You can find a $k$-clique in $n^k$ time by examining all possible sets of vertices of size $k$. So why is it NP-complete to determine if there is a clique of size greater than $k$? It looks like you ...
1
vote
2answers
139 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
1
vote
0answers
72 views

What is the difference between the Big O and Big O star (asterisk) operator?

I'm doing some research on algorithms complexity and in different papers I notice both the use of the regular Big-O operator O(...) and a variant ...
1
vote
1answer
38 views

Calculating algorithmic complexity

Given the following bit of code, how would I calculate the complexity? ...
4
votes
1answer
50 views

Complexity of factoring non-squarefree numbers

Consider the two numbers $N_1=p_1\cdot p_2$ and $N_2=p_1^2\cdot p_2$, where $p_1$ and $p_2$ are primes. Is there any factoring algorithm that can factor $N_2$ faster than the asymptotically fastest ...
1
vote
3answers
290 views

Big O notation - Proving that a function is not O(n)

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$. I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$. Many ...
1
vote
1answer
46 views

Odd way to do arithmetic

If I want to divide $9251$ by $29$, the methods taught in elementary school suffice. Now suppose I want the prime factorization of $9251$. The square root of that number is between the consecutive ...
0
votes
0answers
21 views

complexity of an optimization problem

Consider $n$ variables $x_1, \cdots, x_n$ with the constraint $\sum_{i=1}^n x_i=1$ and $x_i\geq 0$. I want to minimize $\vec{a}^T (I-\alpha A(\vec{x}))^{-1} \vec{b}$, where $\vec{a}$ and ...
3
votes
3answers
141 views

Why are the hierarchy theorem proofs called diagonalization?

Proofs of the various hierarchy theorems in theoretical computer science (see e.g. http://www.cs.princeton.edu/theory/complexity/diagchap.pdf) are usually called diagonalization proofs. Why they are ...
0
votes
0answers
47 views

How can I find the distribution of a recursive relation with two parameters?

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also ...
2
votes
2answers
103 views

number of strictly increasing sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$?

What is the number of strictly incremental sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$ ? Is there any exact value? How about approximations?
0
votes
0answers
29 views

any approximation for $\sum_{i_3=3}^{n-k+3}\sum_{i_4=i_3+1}^{n-k+4}\sum_{i_5=i_4+1}^{n-k+5}\cdots\sum_{i_k=i_{k-1}+1}^{n} 1, (n \gg k)$?

Is there any approximation for $$\sum\limits_{i_3=3}^{n-k+3}\sum\limits_{i_4=i_3+1}^{n-k+4}\sum\limits_{i_5=i_4+1}^{n-k+5}\cdots\sum\limits_{i_k=i_{k-1}+1}^{n} 1, \quad (n \gg k)$$ ? We know that ...
0
votes
1answer
28 views

Adding a point to shortest path

If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ...
2
votes
3answers
74 views

Determine appropriate $c$ and $x_0$ for Big-O proofs.

"Prove that $f(x)$ is $O(x^2)$:" $$f(x) = \frac{x^4+2x-7}{2x^2-x-1}$$ Let $c=10$ (addition of coefficients of the numerator less the addition of coefficients of the denominator), and $x_0 = 1$ (the ...
1
vote
1answer
64 views

What's wrong with this argument for $NP \ne EXP$?

Let $\{M_i\}$ be any enumeration of all Turing machines in which each machine appears an infinite number of times. Consider the language $D = \{i \, | \, M_i(i) \text{ does not accept within ...
1
vote
1answer
28 views

Correctness of complexity analysis of recursive algorithm

Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?
1
vote
1answer
34 views

Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
0
votes
2answers
44 views

Do polynomial bounds on a function imply polynomial bounds on absolute value of the function?

Suppose I know that $f\in\mathcal{C}^{k}(\mathbb{R})$ is such that there exist monic polynomials $P_{1}$, $P_{2}$ of order $k$, that bound $f$: \begin{align*} \forall x\in\mathbb{R}, \ ...
0
votes
0answers
41 views

Quanitified boolean formula and equality of P=NP

This is an exercise problem in "Computational complexity: A modern approach" Let Σ2 SAT denote the following decision problem: given a quantified formula ψ of the form ψ = ∃x∈{0,1}n ∀y∈{0,1}m s.t. ...
0
votes
1answer
42 views

how to show a function is negligible

Let neg(x) be a negligible function. Let p be a polynomial function such that p(k)≥0 for all k>0. What can we say about f = neg(p(k))? Is f a negligible function? If yes, then is there ...
1
vote
1answer
24 views

Showing for $f,g:\mathbb{R}\rightarrow\mathbb{R}$ that for $M>0, |f(x)|\le M|g(x)|$ for $x>x_0$

Showing for $f,g:\mathbb{R}\rightarrow\mathbb{R}$ that for $M>0, |f(x)|\le M|g(x)|$ for $x>x_0$. This is a repost of a question that is probably too long to ever get an answer (I feel compelled ...
1
vote
2answers
112 views

Are all undecidable problems NP-Hard?

So, I need answer to question in title: Are all undecidable problems NP-hard? What I mean is if I have some undecidable problem (for example, Post correspondance problem) can I say it's NP-hard and ...
1
vote
0answers
47 views

number of multiplication steps required to solve Ax = b

If we can factorize $A$ in $LU$, We can solve $Ax = b$ in 2 steps: Solve $Lc = b$ for c Solve $Ux = c$ for x As per the Linear algebra book by Gilbert Strang, each step takes $n^2/2$ number of ...
1
vote
1answer
45 views

Complexity class with arithmetical oracle.

Although I feel the answer to the following question is negative, I can't get any precise results neither find anything to read. The question is: Would a complete oracle from some level of ...
0
votes
0answers
18 views

Reducing the complexity of a Combinatoric Equation

Given the equation: $$ P = \sum\limits_{n=1}^{\lfloor {\frac{q}{2}} \rfloor} {\dbinom{2n-1}{\frac{W}{2t}+n-1}\frac{1}{2^{2n-1}}} $$ Are there any algebraic tricks (or any others for that matter) ...
2
votes
1answer
59 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
1
vote
0answers
42 views

Computational Complexity

My question is very basic, it is just so that I have a basic grasp of the terminology of algorithm speed. When someone says an algorithm speed is $O(n^2)$ they say that the number of steps of this ...
0
votes
3answers
40 views

Reference for problems without efficient algorithm (in polynomial time)

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have: -Boolean satisfiability ...
1
vote
1answer
32 views

Complexity of the Automorphism problem in group with polynomial growth.

Do we have any characterization of groups with a decidable automorphism problem ? When it is decidable, Is there any results about the complexity of the automorphism problem in group with polynomial ...
1
vote
0answers
52 views

Implications of NP=coNP for PSPACE

If NP = coNP, then the Polynomial Hierarchy collapses to its first level (NP). Intuitively, it seems to me that PSPACE should collapse down to NP as well. As a loose heuristic argument, take the ...
4
votes
2answers
136 views

About theorem's proof length in propositional calculus

In PC(propositional calculus) system, how long will a formula's proof be? That is to say if there exists a computable function $f$ such that for any formula $A$, if $\vdash_{\mathrm{PC}}A$ then $A$ ...
0
votes
1answer
23 views

NP-hardness of an Integer Program

Could someone please explain if it has been proven that the following problem is NP-hard $$\mathrm{maximize}\sum x_i$$ $$A\mathbf x\leq1$$ $$x_i\in\{0,1\}\forall i$$ where $\mathbf x = ...
2
votes
1answer
81 views

Why is NP not equal to P^NP?

If something can be decided in polynomial time with an NP oracle, why isn't it in NP? You would think that if you ran a polynomial-time nondeterministic Turing machine polynomially many times, that ...
2
votes
2answers
64 views

np or np complete proof of a factory problem

Good evening everyone; I face with this problem and I could not find a way to proof it. Here is the problem; A={Writing out the factorial of a number in unary NP-complete or NP-hard (e.g. n! = 11 ...
0
votes
0answers
27 views

Matrix scaling problem for Unitary matrices

I would like to know about the complexity of the following problem. Given a ($n\times n$) unitary matrix U and two row-vectors R and C of rational numbers, all of which less than 1, with ...
1
vote
3answers
42 views

I have an answer for an asymptotic analysis, which i cannot accept. please explain me where i go wrong.

We have the following function definitions: \begin{align*}f_1 (n) &= n^{n^{\frac{1}{2}}} \\ f_2 (n) &= 2^n \\ f_3 (n) &= n^{10} 2^{\frac{n}{2}} \\ f_4 (n) &= \sum_{i=1}^{n} (i+1) ...
3
votes
0answers
38 views

Period of a multivariable function

consider a function $$f(x_1, x_2, \ldots, x_n) $$ is it possible to compute the period of the function as a vector $$\langle l_1, l_2, \ldots, l_n\rangle$$ where each $l$ denotes the period of the ...
5
votes
1answer
105 views

What is the simplest collatz like problem that is undecidable?

I have read that problems resemblings collatz have been shown to be undecidable. Conway proved that apparantly but Im not sure if the proof was constructive. So I wonder : What is the simplest ...
1
vote
0answers
41 views

Is Quadratically Constrained Quadratic Program (QCQP) in NP?

The general version of QCQP is NP-hard, but is it also NP-complete? That means, is there a non-deterministic algorithm, which solves QCQP in polynomial time complexity? If the general version of QCQP ...
1
vote
0answers
32 views

Why every regular language is in $\text{TIME}(n)$?

How can I prove that every regular language $R$ has linear time complexity, i.e. every regular language satisfies $$R \in \text{TIME}(n)$$
0
votes
1answer
70 views

Word-chain game complexity

There's a popular game, when two people each after each call cities in such a way that every next city begins with the previous one's last letter. For, example: A: Washington B: New Orleans A: Syndey ...