Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

0
votes
0answers
14 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 ...
0
votes
0answers
22 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 \;|\; ...
4
votes
0answers
104 views
+50

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
30 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
152 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}...$ ...
8
votes
2answers
163 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
24 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
30 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
75 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
146 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
12 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
17 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
10 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
41 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
37 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
102 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
37 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
51 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
55 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
37 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
29 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
127 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
68 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
40 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
28 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
77 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
40 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
2
votes
2answers
71 views

Solving the equation $n\log n = 10^9$

This seems very basic (I guess my calculus needs brushing up). Is there a way to find n without a calculator in this one? $10^{9} = n\log(n)$ My Attempt (log is base 2 base on the book convention.) ...
-2
votes
1answer
29 views

How long would it take to test all possible states of a 64x64x64 cube of bits?

Imagining a solid cube of $64 \times 64 \times 64$ bits (each of which can have exactly two states), how long would it take to test all possible states of one of these? Let's also assume we're using ...
0
votes
0answers
62 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
1
vote
0answers
25 views

Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
0
votes
0answers
13 views

Linear-bounded Turing Machines

What is the class that contains linear-bounded Turing machines? Is it possible to diagonalize on this class? And is there any Universal linear-bounded Turing machine that can simulate linear-bounded ...
0
votes
0answers
17 views

$P=NP \Rightarrow P(S)=NP(S)$?

If $P=NP$, then is it possible to conclude that for every sparse set $S$, $P(S)=NP(S)$? ($P(S)$ means a class of sets for which a Polynomial Deterministic Turing Decider with Oracle Set $S$ exists, ...
0
votes
0answers
29 views

Hardness of bounded modular square root of 1

If we know any square root of 1 modulo N different from 1 and N-1, then we can find a nontrivial factor of N. So to find such a square root has a certain hardness. In fact, if in general we ask to ...
1
vote
2answers
30 views

math rules when having 2 variables in Big-O

I came across the following in some lecture notes: O(log n) + O(log m) = O(log n + log m ) = O(log (m + n)) that last step to ...
6
votes
1answer
34 views

Integer programming feasibility is NP-what

What is the complexity class of the general problem of integer programming feasibility? The sources I've looked at are, in my opinion, very confusing. Some say NP-hard, some say NP-complete. Some ...
1
vote
1answer
32 views

How on earth will anyone prove $n^3-3n^2+n-1=Θ(n^3)$

I know its homework question.Sorry for that.But i was solving all problems of Skiena and chapter and got stuck to this problem of 2nd chapter 2.10. Its easy to prove $n^3-3n^2+n-1=O(n^3)$ because ...
1
vote
1answer
24 views

What's the complexity of expanding a general polynomial?

Suppose I have a polynomial in the form $(a_1 x_1+ a_2 x_2+...+ a_m x_m)^n$, where $x_1,...,x_m$ are the independent variables. I want to expand it to the form of sum of products. What is the ...
0
votes
0answers
46 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
0
votes
1answer
21 views

Double sigma summation is in complexity calculation

Basically i was reading skiena and doing exercise of 2nd chapter.The result of my calculation got differed from the actual solution given on Solution site and there is one thing i don't understand how ...