Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

3
votes
2answers
59 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
0answers
30 views

Is complexity change when multiply with some number

The power operation with modulo operation $a^b \mod n$ has time complexity $O(\log n)$. what happen when it is multiplied with a number $p·a^b \mod n$, it can be read as $(p \mod n)(a^b \mod n)$. Is ...
1
vote
1answer
31 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
37 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
27 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
73 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
30 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
35 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
29 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
41 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 ...
0
votes
1answer
47 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
0
votes
1answer
40 views

Logic & Computability Problem

i read this sentence in one exam that be false. anyone could say why? if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate.
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
26 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
61 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 ...
0
votes
0answers
13 views

(Algorithm complexity) Find properties of ≪ relation

I got a exercises related to algorithm complexity analysis as below ...
1
vote
0answers
24 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
11 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
16 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
27 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
29 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
33 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 ...
0
votes
0answers
20 views

computational complexity of $\sum_{k=1}^K {n\choose k}$

I would like to know what is the computational complexity of $n\choose k$ and $\sum_{k=1}^K {n\choose k}$ in terms of $\mathcal{O}$.
1
vote
1answer
31 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
23 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
39 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
0answers
32 views

L={(M,W) | M is a Turing Machine that stops on input W } is not R. E.

I've been thinking about how to show this but I'm stuck. on Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific ...
0
votes
1answer
17 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
39 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
10 views

Polynomial-time reduction and complexcity sets P and NP.

hello I am having difficulties to understand the topic of P,NP and Polynomial-time reduction. I have tried to search it on web and ask some of my friends , but i havent got any good answer . I wish ...
0
votes
0answers
26 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
24 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
18 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
58 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 ...
1
vote
1answer
18 views

Trying to prove something in complexity

I just started to learn about complexity-theory, and I'm trying to prove this: If P=NP, then every (non-trivial) language in P is NP-complete. Can someone give me a solution please?
0
votes
0answers
22 views

Complexity of and an algorithm for finding ideals of a ring?

One of the problems that has been a roadblock in my understanding of ideals has been how one would find them. One way of finding an I of some ring R would be to say $ \forall x \in I, \forall r \in R ...
0
votes
1answer
41 views

Prove in complexity theory

Given a language A, which is in NP and also not NP-complete, I have to prove that P != NP. [Note: A is not trivial] Any suggestions?
0
votes
2answers
66 views

$O(n^{\log(n)}) $ time algorithms

Is $O(n^{\log(n)}) $ time algorithm considered of exponential time ? Is it applicable ?
1
vote
1answer
31 views

Generalization of Jacobi symbol for higher powers?

Let $n$ be an odd positive integer of unknown factorization, and let $x$ be relatively prime to $n$. The Jacobi symbol $\left(\frac{x}{n}\right)$ gives me partial information on whether $x$ is a ...
1
vote
0answers
10 views

Find a simple Theta bound for a geometric series

I'm working on a question like: find a simple g(n) (big theta) for $ f(n) = \sum _{i=1}^n 5^i $ My working starts with this $\frac{5-5^n}{1-5}$ which is not equivalent to the correct answer from ...
0
votes
1answer
21 views

Complexity class notation

In my CS courses we often use Big-O notation to denote the complexity of a certain calculation. However, we often also write stuff like: $$mO(1) = O(m),$$ or: $$O(m) + O(n) = O(m+n) = ...
0
votes
1answer
17 views

Computational complexity of numerical integration of gaussian function

$ \int^{b}_{a} \exp(-x^2)\,dx$. I have the following two questions regarding the above integral expression of the Gaussian function: Is there a numerical method we can use to solve the above ...
0
votes
0answers
50 views

Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
2
votes
2answers
44 views

Problem on time complexity

If $a = O(m)$ and $b = O(n)$, is it true that $a+b = O(m+n)$? I would try to break it down to $a \le cm$ for some $c$ and $b \le dn$ for some $d$, so if I were to add the right hand side, it would be ...
0
votes
0answers
34 views

Is there a fast algorithm for computing the $(2^n)+1$ th last digit of $3^{2^n}$ in base $2$?

Is there an algorithm such that for some polynomial p, it always computes the $(2^n)+1$ th last digit of $3^{2^n}$ in base $2$ in at most p(n) steps for all nonnegative integers n? I'm only asking if ...
1
vote
1answer
72 views

Mixed Q horn SAT

I am familiar with Horn formula: Formula whose clauses have atmost one positive literal. I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn. Question 1: But, ...
0
votes
2answers
25 views

Multiplying Big-Os

I've seen the following in a text: $\mathcal{O}(\sqrt{n})\cdot \mathcal{O}(n\log n)$ How is that even defined? Ok, I guess one can replace it with: $\mathcal{O}(\sqrt{n} \, n\log n)$ Is that ...
0
votes
1answer
16 views

Find subset sum problem verifier and its complexity

As homework we need to find a P-verifier for the subset sum problem. Given: natural numbers $a_1, \cdots, a_n$ and $b$ Output: YES if there is a subset $S \subseteq \{a_1,\cdots,a_n\}$ where ...
0
votes
0answers
43 views

Master Theorem and Logarithms

I am really struggling to understand the Master Theorem when in a formula: T(n) = aT(n/2) + f(n) f(n) takes the form of log(n), nlog(n) or nlog^k(k) For ...