Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

1
vote
1answer
94 views

Cover the n-sphere with sub-hemispherical caps

Original Question (answered): Define a cap (x,Phi) to be the set of all points of the sphere that are within an angle Phi of the point x. $ 0 \le \phi < \frac{\pi}{2} $. (define the angle ...
0
votes
0answers
101 views

Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
0
votes
3answers
64 views

Prove or disprove: $n\log ({2^n}\log ({n^2})) = O({n^2})$

Prove or disprove: $$n\log ({2^n}\log ({n^2})) = O({n^2})$$ What I reached so far is: $$\eqalign{ & n({\log _2}{2^n} + \log ({n^2})) = \cr & n(\log n + \log ({n^2})) = ? \cr} $$
2
votes
1answer
106 views

Finding no-self-intersecting path in geometric graphs

Is there a polynomial algorithm to determine whether there exists no-self-intersecting path between given vertices $s$ and $t$ in a geometric graph $G$? Geometric graph is an image of a graph on a ...
3
votes
1answer
42 views

What is the complexity of $\Theta((n^3)/(\log(n))^4)$ ? Or $\Theta(n \cdot (\log(n))^3)$?

What is the complexity of $\Theta\big(\frac{n^3}{\\(log(n))^4}\big)$ ? Or $\Theta\big(n \cdot (\log(n))^3\big)$? Is the first one equal to $\Theta(n^3)$?
0
votes
0answers
24 views

Analysis of the successive elimination algorithm for multi-armed bandits

I'm referring to page 7 (page 11 if you look at printed page numbers) of http://moodle.technion.ac.il/pluginfile.php/328871/mod_resource/content/1/Chapter1_bandits.pdf Here's what he claims, and I'm ...
0
votes
1answer
34 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
5
votes
2answers
201 views

NP-complete: One proof to rule them all

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown: There is a polynomial verification for $C$ solution. Every problem in NP is reducible to $C$ - You can solve all the ...
0
votes
1answer
31 views

Valid proof regarding complexity class?

Consider $L \in BPP \cap NP$. Every string $x \in L$ can be accepted with probability 2/3 since $L \in BPP$. Every string $x \not \in L$ can be rejected with probability 1 since $L \in NP$. This is ...
2
votes
3answers
53 views

Best Sum of Three Elements in a Sequence

I encountered the following problem: Given an integer sequence $\left(s_1,s_2,\dots,s_n\right)$ and an integer $l$, find $$\min\left|s_i+s_j+s_k-l\right|,$$ where $i\neq j\neq k\neq i$, and return ...
1
vote
1answer
122 views

Time complexity of binary sum

What is the time complexity of binary sum, the sum of two binary numbers done like in elementary school? Say one number is F and his length is $s$ bits, and another number is H and his length is $t$. ...
-2
votes
2answers
71 views

How prove big O notation?

How to prove this function 1). $f(n)=n^3 − 5n^2 + 25n - 165$ is $O(n^3)$. 2)$3+\sin(1/n)$
-3
votes
1answer
48 views

Union Find Program Prove By Induction

Consider the program below for building a union-find data structure. Prove by induction that if the method build_union is called starting with each vertex in a component by itself, that the ...
1
vote
0answers
83 views

A question on the computational complexity of Boruvka's algorithm

One algorithm that finds a minimum spanning tree in a graph in which all weights are distinct is Boruvka's Algorithm (also known as Sollin's Algorithm). On the page you would see once you clicked ...
1
vote
1answer
42 views

How to prove that $n^{\log_{2} (n) } = O (2^n) $ ?

While trying to prove that $$ n^{\log_{2} (n) } = O (2^n) , $$ I figured that $$ 2^n = e^{ n \ln (2) } , $$ and that $$ n^{ \log_{2} (n) } = n^{ \frac{\ln(n) }{ \ln(2) } } = e^{ \ln (n^{ \frac{ ...
1
vote
1answer
46 views

Is this minimization problem NP-hard?

Given an $m*n$ positive matrix $\mathbf{A}$ and an integer $K$, where $0<K<n$. Now, I have a $m*n$ binary matrix $\mathbf{B}$. I need to dertermine the value of each element in matrix ...
0
votes
1answer
58 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
1
vote
1answer
32 views

Is $O(n \log n)$ always smaller than $O (m)$ for $n-1 < m < n^2$?

I am writing an algorithm that needs to finish in $O(m)$. The problem is for a graph $G( V, E )$, where $m = |E|$ and $n = |V|$. $m$ can be in the range of $n-1$ to $n^2 - 1$. If I do some ...
3
votes
1answer
78 views

Computational Complexity of Finding Adjacent Terms in Farey Sequence

The Farey sequence $\mathcal{F}_n$ is the list of all fractions in increasing order (in lowest terms) from $0$ to $1$, having denominator at most $n$. My question is, given some $a/b\in\mathcal{F}_n$ ...
3
votes
1answer
80 views

On the existence of an injective recursive function such that all its values are also its indexes.

Kleene's second recursion theorem easily yields a self-referential program. What is more, it gives a program $P_a$ that computes any computable function of its index $a$ and its input. But does an ...
1
vote
0answers
77 views

How to prove the NP-hardness of this scheduling problem

Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations ...
1
vote
0answers
131 views

How to compute this recursion in linear time?

Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ ...
1
vote
0answers
16 views

The $k$-th term in the graded lexicographical order is recursive

I recently constructed a proof that a computable universal function exists for the class of polynomials of $n$-variables. To this end, I adopted the graded lexicographical monomial order. However, I ...
0
votes
0answers
7 views

Determining if a Language is contained in P, based on two representations of max runtime

Is the language L1 = {(M, w, 1^t) | M accepts w after running for max t steps} contained in the class P? I know that there are 2 main goals: runs in polynomial ...
1
vote
1answer
58 views

Do this algorithm terminates?

Let $x \in \mathbb{R}^p$ denote a $p$ dimensional data point (a vector). I have two sets $A = \{x_1, .., x_n\}$ and $B = \{x_{n+1}, .., x_{n+m}\}$. So $|A| = n$, and $|B| = m$. Given $k \in ...
0
votes
0answers
9 views

Polytime integral approximations in $n$ variables

Let $A = [0, 1]^n$ ($n \approx 16$ for my purposes). I have a function $f$, and I can query $f(x)$ in constant time. I want to computationally approximate $\int_A f(x)$. The natural solution is the ...
1
vote
1answer
94 views

Complexity of the algorithms for Singular Value Decomposition

As said in the title, I would like to find out something on the numerical algorithms for computing the SVD decomposition of a rectangular matrix, with particular regard to their the computational ...
0
votes
1answer
31 views

Weighted Union Find

Prove that the weighted union (w_union) takes O(log2(n)) for FIND in the worst case on a graph which has n nodes by proving by induction. I'm not sure how I would prove this at all, I know how I ...
1
vote
1answer
56 views

The history function preserves recursiveness

Starting with an effective coding of the lists of numbers, I recently proved that concatenation of lists is primitive recursive. On the way I used that if a function is primitive recursive, then its ...
0
votes
1answer
27 views

Time complexity comparison

I'm struggling with these 2 questions: What are the relations $(\mathcal O, \theta, \Omega)$ : $\quad\text{a.}\,$ $\log(n!),n\log(n)$ $\quad\text{b.}\,$ ...
0
votes
1answer
25 views

Compute all the directional derivatives of a trivariate polynomial function quickly

Given a trivariate polynomial $A\in\mathbb{R}[x,y,z]$, a direction $\vec v\in\mathbb{R}^3$ and a point $p\in \mathbb{R}^3$, what is the fastest way to compute the directional deriviatives ...
1
vote
2answers
140 views

How do I grade the complexity of the below math puzzle game?

The game (I built it, and it is currently live on mobile) involves solving a pascal's triangle like grid of numbers with operators between the numbers - an example with 3 rows is: ...
1
vote
0answers
59 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
0
votes
0answers
21 views

Time complexity of combinatorial number? [duplicate]

What is the time big-oh complexity of the following combinatorial number? $$\binom{h+m-1}{m-1}.$$ where $h \gg m$. I guess that it is $O((h+m)^{m-1})$. Thank you very much.
1
vote
1answer
45 views

Amortized analysis and the potential method

To my understanding to use the potential method to get the amortized cost of an operation the following conditions need to be satisfied: $\Phi (D_{0}) = 0$ $\Phi (D_{i}) \geq 0$ for all $i \geq 0$ ...
0
votes
1answer
67 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
0
votes
1answer
33 views

Computational complexity of Newtons Method

I'm trying to do a worst case complexity analsis of another algorithm that involves computing an nth root of a real number at each step. I have a bound B on the size of this number also n is fixed and ...
2
votes
2answers
68 views

Prove that $6^{\sqrt n} = O({n \choose n/2})$

Prove that $6^{\sqrt n} = O({n \choose n/2})$ I was able to show that prove that $6^{\sqrt n} = O({n \choose n/2})$ with defining $ n=2k$ and $ a_k= \frac {k!^26^\sqrt k} {2k!} $ and then show ...
1
vote
1answer
53 views

prove\disprove - there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$

there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$ Thought about $f(n) = |sin(n)|,\ g(n)= \frac1n$ then $f(n-g(n))= |sin(n-\frac1n)|$ and then for any ...
0
votes
1answer
51 views

Upper and Lower Bounds

The question that I'm having trouble with is: Prove that k/2 is a lower bound for √(n) I'm not sure how I would start this, can someone take a look at it and help me with it? I understand the ...
2
votes
0answers
70 views

Number of orderings of subset sums

In short: In how many ways can all $2^n$ subset sums of $n$ real numbers $a_1,\ldots, a_n$ be ordered? I am not concerned about the case in which different subsets sum to the same number; you may ...
0
votes
1answer
75 views

Solve linear programming given access to an oracle

This question is about designing a polynomial time algorithm for linear programming given access to an oracle outputs YES if and only if $\{\vec{x}\ |\ A\vec{x} = \vec{b}, \vec{x}\geqslant ...
1
vote
0answers
64 views

Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
1
vote
4answers
108 views

What is an example for an algorithm which makes use the power of randomness?

Can someone give a (most simple) example for an algorithm on a machine, which has access to random numbers, and which is faster than any other known algorithm for the same task? My actual motivation ...
8
votes
2answers
355 views

Why are Polynomial Time Problems Considered Tractable, and Larger Times are Not?

I've been reading up on $P=NP$, problem tractability, etc. Here's my question: Why is it that we consider problems that can be solved in polynomial time - or algorithms/problem-solvers running in ...
0
votes
1answer
27 views

Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
0
votes
0answers
265 views

Exact inversion of matrix complexity (by Gaussian elimination)

I would like to check if what I have done is correct. Please, any input is appreciated. Problem statement: Consider a non-singular matrix $A_{nxn}$. Construct an algorithm using Gaussian elimination ...
2
votes
1answer
116 views

If P = NP, then 3-SAT can be solved in P

Prove that if $P = NP$, then there is an algorithm that can find a boolean assignment for a 3-SAT problem in P time if it exists. $P = NP$ only says that we can decide whether a 3-SAT problem is ...
0
votes
1answer
39 views

Prove a language is NP-Complete

$A$ is NP-complete. $B$ is P. $A \cap B = \emptyset $ $A \cup B \neq \sum^{*}$ Prove that $A \cup B $ is NP-complete. How can I prove this ? I think if anything can be P-reducible to A then it ...
4
votes
3answers
91 views

$NP$ problems not known to be in $P$ and not known to be $NP$-complete

I've read that solving Pell's equation is neither known to be in $P$ nor known to be $NP$-complete. What are other natural and important examples of such problems?