Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

2
votes
1answer
25 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
76 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
16 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
21 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
29 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
24 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 ...
0
votes
1answer
33 views

Analyze the following recurrence relation.

I'd like to express the following recurrence relation as the number of multiplications it performs, and then again but this time as the number of additions/subtractions it performs. ...
1
vote
1answer
26 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
43 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
62 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
11 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
20 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
10 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
27 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
290 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
35 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
161 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
7 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
169 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
33 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
87 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
153 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
47 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
11 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 ...
0
votes
0answers
42 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
0
votes
1answer
39 views

Variant of the Halting Problem

S = {$<A, B, k>$ : there are less than k natural numbers n for which A(x), B(x) both halt} I have the following proof that S is undecidable. Suppose D($<A, B, k>$) is a decider for S. ...
1
vote
4answers
121 views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
0
votes
1answer
39 views

Betweenness Centrality: How Long Does Mathematica Take?

A simple maths problem. If I have a disk of unit radius and place within it $N$ nodes such that the node density $\rho$ is given by $$\rho=\frac{N}{\pi R^{2}}=\frac{N}{\pi}$$ then connect each node ...
1
vote
1answer
72 views

$NP^{PP} vs. PP^{NP}$, which one subsumes the other?

I understand why P with an NP oracle ($P^{NP}$) subsumes $NP$: because it contains co-NP. But how about NP with a P oracle? Can it be any different from NP? (I'm guessing they are the same otherwise ...
1
vote
2answers
54 views

Proving Hamiltonian Cycle is NP Complete

I'm trying to learn Complexity classes.I want to show Hamiltonian cycle is NP Complete. The text tells me that Inorder to prove NP-Completeness we first show it belongs to NP,by taking a ...
1
vote
0answers
60 views

GCD of high order polynomials(modulo large prime)

I want to solve the following question: Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...
0
votes
0answers
40 views

sorting young's tableau better than n^3

Young's tableau takes $O(n^3)$ to sort. By sorting I mean sort numbers in existing young's tableau. http://en.wikipedia.org/wiki/Young_tableau Simply it is a matrix sorted by rows and columns. ...
0
votes
1answer
30 views

Formulating the Twin Prime Conjecture as a Language Recognition problem.

I'm trying to figure out how to formulate the Twin Prime Conjecture as a language recognition problem. I've got: A = {p: p is the largest prime such that p + 2 is prime} B = {p: p and p+2 are both ...
1
vote
1answer
134 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 ...
3
votes
2answers
70 views

State-Space Complexity of RISK board game

I want to calculate the (state-space) complexity of the RISK board game. Online I found a thesis that outlines that complexity (page 34). Here is the summary: Let M denote the maximum number of ...
1
vote
1answer
32 views

Understanding an algorithm

I want to understand the above algorithm. My solution says that the algorithm should return $0$ if $n$ is a prime or 1. Otherwise it returns the smallest (positive) non-trivial divisor. Lets ...
0
votes
1answer
41 views

Pumping lemma proof of $L = \{a^nb^m \mid 0\leq n<m\}$

Prove the following language is not regular using the pummping lemma $L = \{a^nb^m \mid 0\leq n<m\}$ I tried solving this problem what I don't think I was able to reach an accurate proof. But this ...
1
vote
1answer
29 views

Transform a k-CNF formulae to conjunctions of boolean literals

The question comes from Mehryar Mohri's Foundations of Machine Learning. In Example 2.5 the book transform a $k$-CNF formula to conjunctions of boolean literals, but I can't understand the trick in ...
4
votes
2answers
78 views

Theoretical computer science text for mathematician

I am a high school student, I know some basic programming in java,python and visual basic. I love combinatorics and I have encountered various cases in which I have found some problems are really ...
0
votes
0answers
14 views

Determine $P_2 = f(0.7)$ when Neville's method is used to approximate $f(0.5)$

Let $f(x) = \ln(x + 1)$. Neville's method is used to approximate $f(0.5)$, giving the following table. $$x_0 = 0 - P_0 = 0$$ $$x_1 = 0.4 - P_1 = 2/8 - P_{0,1} = 3/5$$ $$x_2 = 0.7 - P_{2=?}- ...
1
vote
1answer
31 views

Trying to understand the math in a neuroscience article by Karl Friston

I am trying to understand a neuroscience article by Karl Friston. In it he gives three equations that are, as I understand him, equivalent or inter-convertertable and refer to both physical and ...
0
votes
1answer
41 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
-1
votes
2answers
30 views

Analysis of algorithm about complexity

$n$ is $O(\log n)^{\log n}$ ? This is true or false, Give the reasons behind that ? I dont get understand about that $O(\log n)^{\log n}$.
1
vote
2answers
42 views

How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$ For the first, I don't have a formal proof but I ...
-1
votes
1answer
55 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that