Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

0
votes
0answers
31 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
102 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
59 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
votes
1answer
95 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 ...
3
votes
0answers
59 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 ...
2
votes
0answers
68 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. ...
12
votes
3answers
328 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
138 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
4answers
319 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 ...
1
vote
1answer
37 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
237 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
41 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
95 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
102 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
249 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
60 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
29 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
24 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
1answer
65 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
2k 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
85 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
90 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
2k 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 ...
0
votes
1answer
55 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
180 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
124 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 ...
0
votes
1answer
42 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
212 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
2answers
94 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 ...
5
votes
3answers
194 views

Theoretical computer science text for high-school student

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 ...
1
vote
1answer
45 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
93 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 ...
0
votes
2answers
34 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
50 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
68 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
144 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.) ...
-3
votes
1answer
40 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 ...
2
votes
0answers
42 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
39 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
35 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 ...
7
votes
1answer
68 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
40 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
34 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
50 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
117 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 ...
1
vote
3answers
57 views

Confused with the definition of NP

In the blog post at: Concrete Nonsense I read: NP is the set of problems that can be solved by polynomial-time non-deterministic algorithms. An equivalent definition of NP is the set of ...
0
votes
0answers
34 views

Using the pumping lemma to prove that a certain language is not regular

I've been trying to understand the pumping lemma since forever, I just don't know what it does, I have no clue what any of it does. My college professor sucks, he thinks writing a bunch of stuff on a ...
0
votes
1answer
80 views

What is the time complexity of an $O((\ln n)^{\ln n})$ algorithm?

How can the time complexity of an $O((\ln n)^{\ln n})$ algorithm be simplified and compared to some other time complexities?
0
votes
1answer
34 views

Reduction between languages in P

I have a simple question about the class P: Is there exist a polynomial time reduction between every two languages A, B in P?
2
votes
1answer
67 views

Simple question on complexity

I just started to learn the complexity theory, and I have a simple question: Let's say that there's a language B in NP, such that there's no polynomial reduction from B to a given language A (which ...