Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

1
vote
0answers
13 views

Efficient algorithm to find a minimum spanning set for a given vector.

A few days ago a colleague proposed the following problem. Let $W$ be a finite subset of a vector space $V$, and let $v\in\langle W\rangle$ (the linear span of $W$). Is there an efficient ...
0
votes
1answer
16 views

How to calculate running time of code?

I'm finding great difficulty calculating runtime with loops. It's easy when there is one loop, especially when the counter is being incremented by one: ...
0
votes
0answers
5 views

Lowest complexity matrix multiplication using parallelization

I'm not very familiar with complexity calculations (though I'm trying to learn), but what is the fastest published way to multiply two square matrices together with a GPU? The estimate I can come up ...
-1
votes
0answers
19 views

Prove or Disprove? log(n^n) is Theta(log n)

I need help confirming that my way of proof is alright. This is my first class in algorithms so I just wanna know if I'm on the right track. :)
1
vote
1answer
12 views

Big O complexity of the partition function derived from this code?

I am not able to calculate the Big O complexity of the partition function given in the code below. I tried to calculate it by estimating the number of nodes in the tree. So far, I've figured out that ...
1
vote
1answer
40 views

Finding pair of integers with given modulo

Given integer Goal and S = { X0, X1, ...., Xn } where Xi is a positive integer > 1, find a, b, in S and positive integer n (not necessarily in S) such that: a*n mod b = Goal E.g. Goal = 1, S = {3, ...
5
votes
2answers
68 views

Is $(\log(n))!$ a polynomially bounded function?

Is the following statement true? How would you prove it? i.e. Is it a polynomially bounded? $$ \lceil \lg(n) \rceil ! \in O(n^k) $$ How about $$ \lceil \lg \lg(n) \rceil ! \in O(n^k) $$ Thanks a ...
0
votes
0answers
15 views

random relax based algorithm complexity

consider the follow relax based algorithm than find all the shortest paths from s: input: directed graph G = (V , E) , weight function W:E->R(real numbers), source vertex (s in V). G don't ...
0
votes
0answers
13 views

Problem in complexity class $P$ with highest known degree of a polynomial

Can someone help me find source where is listed complexity of most problems in complexity class $P$, particulary, I would like to know the one with the highest degree found so far. Somewhere I found ...
0
votes
0answers
14 views

Time complexity of semi definite programming solvers?

What is the time complexity of the following semi-definite programming problem ? $$\begin{gathered} \min_{\mathbf z,v}v+\mathbf b^\top \mathbf z\\ \text{s.t. } \mathbf M \succeq 0 \text{ and } ...
0
votes
2answers
25 views

comparing two algorithms and their respective Big O notations

So we learned in classes that some algorithms perform better at certain times. On the homework assignment, We are asked to compare algorithm 1 which takes 4n4 days to run with one that takes 3n ...
0
votes
1answer
15 views

Complexity of FFT Algorithm

OkayI am using iterative FFT algorithm and I have found that since there are 2N computation per stage and there are logN stages the complexity should be O(2NlogN) I can reduce the number of ...
1
vote
1answer
50 views

Complexity of computing $N!$

Question: Complexity of computing $N!$, considering that each multiplication cost about $O(\log^2{n})$. Attempt: There's $n-1$ multiplication. Each multiplication leads to a bigger number, thus $n-1$ ...
1
vote
1answer
67 views

$\Delta_1^1\stackrel{?}{=}FOL$

Let $\varphi$ be a sentence in second order logic that happens to be in $\Sigma_1^1\cap\Pi_1^1(=:\Delta_1^1)$. It is claimed, that $\varphi$ be equivalent to a sentence in first order logic. Is this ...
0
votes
2answers
19 views

Time complexity, proof $\log(n + c) \in O(\log(n))$

I have to prove that for $a \in N, c > 0$ (constants), this statement holds: $\log_a(n + c) \in O(\log_a(n))$ So if I use the definition, the following should hold: $\log_a(n + c) \leq ...
0
votes
0answers
18 views

Find the running time of the following program fragment

The exercise in my book is asking me to calculate the running time of the following for loop: for (int i = 0; i < n; ++i) ++k; This instantly reminds me ...
2
votes
0answers
48 views

Complexity analysis of convex optimization problem

I am studying an optimization problem \begin{equation} \mathbf{x}^*=\text{argmax}\quad\sum_{d=1}^{D}\log(\mathbf{a}_d^T\mathbf{x}+b)+\mathbf{c}_d^T\mathbf{x}+f_d\\ \text{subject to}\quad ...
2
votes
1answer
32 views

Graph pruning whilst ensuring connectivity

Problem: I have a graph (in this instance, it's represented by a matrix which is $\in \mathbb{R}^{n \times n}$). In the raw graph, all nodes are connected to every other node (except themselves) in ...
0
votes
1answer
23 views

Lower Bound Omega Notation

I have to prove that some number $S$ is bigger than $\Omega(|V|)$, where |V| is the number of vertices. I read the definition of asimptotic notations, but I am still confused with the examples. Fot ...
0
votes
1answer
39 views

Basic Question about ambiguity of Grammar

I saw one book in Computation Course. I take a picture from this book, and in this book say why (or not) the following grammar is ambiguous? I couldn't find any solution to prove it's ambiguous. ...
1
vote
1answer
32 views

Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
0
votes
1answer
24 views

Basic Equation question

This is regarding algorith complexity, but that's not the point here. I saw this resolution: 4( n/1,3 )² = 4/1,69 x n² Could anyone clarify how is this ...
2
votes
1answer
26 views

complexity of solving $n \times n$ rank deficient linear system

I think it is known that given a nonsingular $A \in \mathbb{R}^{n \times n}$ and $b \in \mathbb{R}^n$, solving a linear system $Ax =b$ for $x$ can be done in $O(n^3)$ steps. Now assume $A$ is of rank ...
8
votes
1answer
85 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
2
votes
1answer
18 views

Verifier and Certificate for coNP SUBSET-SUM

The original SUBSET-SUM problem is "given a set of integers, is there a non-empty subset whose sum is zero?" If we look at the inverse problem: "given a finite set of integers, does every non-empty ...
1
vote
1answer
23 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
2
votes
1answer
30 views

Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
0
votes
2answers
25 views

Fastest way to find the top points in a rectangle

Given a rectangle X1,Y1 and X2,Y2 such that X1,Y1----------------- | | | | ----------------------X2, Y2 And given a ...
0
votes
0answers
27 views

Decision problem concerning magic squares

What is the computational complexity of the following decision problem ? Given : A list of $n^2$ natural numbers (not necessarily distinct) Question : Is there a magic square containing the given ...
1
vote
1answer
27 views

Algorithm to multiply nimbers

Let $a,b$ be nimbers. Is there an efficient algorithm to calculate $a*b$, the nim-product of $a$ and $b$? The following rule seems like it could be helpful: $$ 2^{2^m} * 2^{2^n} = \begin{cases} ...
1
vote
1answer
48 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
1
vote
1answer
63 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
2
votes
0answers
16 views

Plot implicit equation in sub-quadratic time complexity

It is fairly straightforward to plot an explicit equation such as $y=x^3+3x^2+2x+5$ in linear time, because you can just iterate through all $x$ in your graphing space and use the equation to ...
1
vote
0answers
47 views

Could any one explain the difference between the theorems?

In the paper http://annals.math.princeton.edu/2007/165-2/p04 Theorem 2. Let $b \ge 2$ be an integer. The b-ary expansion of any irrational algebraic number cannot be generated by a finite automaton. ...
0
votes
0answers
21 views

Generalization of standard technique for proving that an undecidable language is unrecognizable

Suppose $L = \{P:P(x) \; outputs \; x^2 \;for\; all\; x\}$ Then $\bar L = \{P: P(x)\; does\; not\; output\; x^2 for\; all\; x \}$. By Rice's Theorem or by reduction from the Halting Problem, let's say ...
0
votes
0answers
13 views

Can this language be solved in PTIME?

I would like to know why we cannot prove that $P \subsetneq PSPACE$ by considering the following language for some particular Turing Machine $M$: $L_M:=$ {$w : M$ accepts or rejects $w$ without using ...
1
vote
0answers
31 views

Language of Specific Grammar

I ran into this exercise in Sipser's Note on Computation Theory. Consider the following grammar $G$: $$\begin{align} S &\to aSD \;|\; bB \\ D &\to dS \;|\; a \\ B &\to bB \;|\; ...
11
votes
3answers
295 views

Eigenvalue test faster than $O\left(n^3\right)$?

Given a real $n\times n$ matrix $A$, one can find the eigenvalues in $O\left(n^3\right)$ by using say, the $QR$ algorithm. Now, what if we guess an eigenvalue $\lambda_0$, and we want to know if it's ...
-1
votes
1answer
37 views

How do I prove that $a = n/2$ is a tight upper bound for the recurrence relation $T(n) = T(n-a) + T(a) + n$?

I have a recurrence relation: $$T(n) = T(n-a) + T(a) + n$$ which happens to be $O(n^2)$ complexity. How do I now prove that: $$a = n/2$$ is a tight upper bound for this relation? I have been ...
11
votes
3answers
166 views

Is there an easy way to find the sign of the determinant of an orthogonal matrix?

I just learned that if a matrix is orthogonal, its determinant can only be valued 1 or -1. Now, if I were presented with a large matrix where it would take a lot of effort to calculate its ...
0
votes
1answer
8 views

Uncountability of the Set of all Infinite Binary Sequences - Diagonalization

One proof of the uncountability of $R$ goes: Suppose a correspondence $f$ exists between $N$ and $R$ such that: $f(1)=m_1.x_{11}x_{12}x_{13}x_{14}...$ $f(2)=m_2.x_{21}x_{22}x_{23}x_{24}...$ ...
9
votes
2answers
173 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
1
vote
0answers
25 views

Is finding a matrix out of some set with a given determinant a hard problem?

Given $n\ge 2\ \ ,\ u,v,k\ $ integers. Decision problem : Does a $n\times n$ - matrix with entries from $u$ to $v$ with determinant $k$ exist? In which complexity class is this problem ? Is it ...
1
vote
2answers
36 views

Is factoring a semiprime easier than matrix multiplication?

I'm currently dealing with complexity estimates of various algorithms and the connected mathematical problems. Up until now, I had in mind that problems such as integer factorization and the discrete ...
4
votes
0answers
89 views

Is it decidable whether the iterates of a polynomial map are bounded?

Let $f:\mathbb{Q}^n\to \mathbb{Q}^n$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates ...
2
votes
2answers
159 views

For recurrence T(n) = T(n − a) + T(a) + n, prove that T(n) = O(n^2 ) complexity

I have been looking over this question for hours now, and can't seem to work it out. It's a question regarding the complexity of sorting algorithms Assume that $a$ is constant and so is $T(n)$ for $n ...
1
vote
0answers
50 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
0
votes
1answer
21 views

Different Forms Of The Halting Problem - Recognizability

There are different versions of the Halting Problem: 1) $\{ P \mid\text{there exists $i$ such that $P$ halts on $i$} \}$, 2) $\{ (P,k) \mid \text{there are less than $k$ inputs that $P$ halts ...
0
votes
1answer
19 views

Different Forms of the Halting Problem

The version of the Halting Problem I'm familiar with is: { (P, i) : P halts on input i } I've seen the following other versions mentioned: 1) { (P, i): there exists i such that P halts on i } ...
0
votes
0answers
13 views

Min cost flow problem for hypergraphs and multidimensional assignment problem

Multidimensional assignment problem is NP in general. There is an algorithm, which transforms the common assignment problem into min-cost flow problem. Why we can't do the same operation onto ...