Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

1
vote
0answers
32 views

Constructing a “one-way function” of two variables (a.k.a “stop my friend from hacking my game”)

This might be more of a computer science question than a mathematics one; I thought I'd start here but perhaps people might want to point me to a better forum, if this isn't the right one. ...
0
votes
1answer
22 views

Proving $\lg n!=\Omega(n\lg n)$

In the answer given in the book for the proof of $\lg n=\Omega(n\lg n)$ there are several steps which I don't understand . $$\lg n!=\lg n+\lg(n-1)+\lg(n-2)+ ....+\lg(2)+\lg 1$$ Then it says that ...
0
votes
1answer
30 views

Does this loop run in $\mathcal{O}(n^4)$ time?

A double loop is given: int sum = 0; for (int i = 0; i < N*N; i++) for (int j = i; j < N; j++) sum++; My analysis: The inner loop runs $n$ ...
0
votes
2answers
39 views

Is my method of computing the running time correct?

Okay, so this is the code for which I need to compute the running time: ...
6
votes
1answer
693 views

If an unary language exists in NPC then P=NP

I've a question regarding a theorem in Complexity Theory. It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct. It means that there exists ...
2
votes
1answer
33 views

Expected Value on code

I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements ...
0
votes
1answer
54 views

What is the probability the best case occurs? (Comp Sci Type Question)

I'm having trouble figuring out what's the probability the best case occurs? It's my first time bringing together probabilistic knowledge into computer science. The question goes as such. Consider ...
0
votes
1answer
44 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
1answer
16 views

How to derive time complexity of following method.

I have one algorithm for which I have to find time complexity of number of time x=x+1 is executed: j=n; while(j>=1){ for i=1 to j x =x+1 j=j/2 } What ...
0
votes
0answers
31 views

Find two element $x_k$ and $x_l$

Let $S=\{ x_1, x_2, \dots, x_n \}$ a set of real numbers, where $n \geq 2$. Describe an algorithm, that has time complexity $o(n^2)$ and that finds and returns two elements $x_k$ and $x_l$ of $S$, ...
1
vote
0answers
31 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 ...
1
vote
1answer
22 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 ...
0
votes
0answers
7 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
22 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
43 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
70 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
16 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
15 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
29 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 ...
1
vote
1answer
69 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 ...
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$ ...
0
votes
1answer
17 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 ...
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 ...
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
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 ...
2
votes
1answer
277 views

what is the relationship between the complexity class E(and EXP) and NP?

I want to know any relationship between the complexity class E(and EXP) and NP. I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size ...
0
votes
1answer
24 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
34 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
31 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$ ...
2
votes
1answer
21 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 ...
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 ...
3
votes
2answers
1k views

what is the computational complexity of solving a quadratic program with linear inequality constraints

I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
1
vote
1answer
24 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})$?
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
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
29 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
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 ...
11
votes
3answers
296 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 ...
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
48 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
14 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
32 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 \;|\; ...
1
vote
1answer
141 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...