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)

1
vote
3answers
56 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
76 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 ...
1
vote
1answer
26 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
32 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
48 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
81 views

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

Is $O(n^{\log(n)}) $ time algorithm considered of exponential time ? Is it applicable ?
1
vote
1answer
56 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
109 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
27 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
84 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
533 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
49 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 ...
1
vote
0answers
38 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
116 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
27 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
35 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 ...
1
vote
0answers
33 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
-2
votes
1answer
59 views

Prove that $\log n = O(\log^2 n)$

Trying to solve this, but I can't seem to figure it out. Its fairly straight forward.
-2
votes
1answer
71 views

Blum's axioms and the space complexity measure

I'm asked to prove that the measure $\Gamma_e(x) = s ~ ~ \iff ~ ~ \varphi_e(x)$ uses exactly $s$ work tape cells (i.e. once it halts, the number of tape cells used by a Turing machine to compute it is ...
1
vote
1answer
41 views

Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$ Thanks!
0
votes
1answer
33 views

Why $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$?

I was told that the complexity of $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with ...
4
votes
0answers
88 views

How to efficiently calculate $ax+b$ once I know $a$ and $b$?

What's the cheapest way to calculate $ax+b$ several times once I know the values for $a$ and $b$? For instance, the cheapest way to calculate $ab+x$ several times once I know the values for $a$ and ...
2
votes
1answer
78 views

Checking if a graph is bipartite is $O(n)$

It seems to me that checking if a graph is bipartite (or biclique) has deterministic time complexity $O(n)$, where $n=|V|^2$, since we clearly have to iterate over all the elements of the incidence ...
1
vote
1answer
152 views

Is NP countable?

Is NP countable? I am confused with this problem. I think it is not countable but I am not sure. Can someone prove whether it is countable? Please show your proof. Thank you for your time!
0
votes
2answers
62 views

key generation in RSA cryptosystem: why it can be performed in polynomial time?

Suppose that I want to generate the keys of the RSA cryptosystem: the public key will be the couple $(n,e)$ where $n$ is the product of two primes $p$ and $q$ and gcd$(\phi(n),e)=1$.The private key ...
1
vote
1answer
206 views

Solving recurrence relation: f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3

f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3 I have attempted to solve it by letting n = 2k f(2k) = 3f(2k-1) - 2f(2k-2) Then set S(k) = f(2k) S(k) = 3*S(k-1) - 2*S(k-2) ...
2
votes
0answers
44 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
0
votes
1answer
32 views

Why does $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$ imply $T(n)=\mathcal{O} (n\log(n))$

I am learning about sort algorithms and their complexities. For merge sort, I'm confronted with $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$. The author makes the claim with no ...
1
vote
0answers
102 views

Proving context free language membership is $P$ complete with respect to log-space reductions

This is exercise from Introduction to Automata theory, Languages and Computation, by Hopcrof, Ullman (first edition). I found example of polynomial reduction to some problems in logic, or graph ...
0
votes
1answer
35 views

Efficiency LL and LR parsing

My question is, is an LL parser or an LR parser more efficient (in big-O terms) ? I don't mean in terms of coding the parser, but rather in the context of the runtime of the parser. Is there a ...
0
votes
2answers
33 views

How can I identify that an instance of Boolean SAT problem remains hard or not?

While I was studying SAT problem and its different instances, in Algorithms for the Satisfiability (SAT) Problem: A Survey by J. Gu et. al PDF, I came up with this instance, not mentioned there, but I ...
1
vote
4answers
49 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
1
vote
1answer
69 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
1
vote
0answers
26 views

Basic questions about descriptive complexity

I'm trying to learn descriptive complexity, and I'm having trouble on a basic level wrapping my head around what it means for a logical formula to define a computational language. I've tried and ...
0
votes
0answers
32 views

How to prove this polynomial expression.

Let the polynomial be in $f$ be a map from $\Bbb{Z}_2^k \to \Bbb{Z}_2$, defined by $f = 1 + \sum_{i=1}^k x_i + \sum_{i\neq j; i,j = 1}^k x_i x_j + \dots + x_1 x_2 \cdots x_k$ Then I want to show ...
0
votes
1answer
43 views

Properties of smallest expressions for polynomials, and potential proof.

See here for an intro. Smallest expressions for polynomials is analogous to smallest grammars for strings. Let $R = \Bbb{Z}_p[x_1, \dots, x_k]$. My goal is to prove that for any $\ \ h(k,p) = \max ...
0
votes
2answers
358 views

Linear search average-case complexity?

I am trying to find the average case complexity of the linear search. I know the answer is O(n), but is this correct: The first element has probability $1/n$ and requires 1 comparison; the second ...
2
votes
0answers
38 views

Is there any oracle A s.t. NP$^A$ $\neq$ EXP$^A$

I think the answer is yes because we do not know whether NP = EXP. But i couldn't find one.
2
votes
2answers
63 views

I want to know an estimate of $a_{i, j}$

Let $$ a_{ij} = \begin{cases} -1, & \text{if $i = -1$ and $j = -1$} \\ 1, & \text{if $i = -1$ and $j \ne -1$} \\ 1, & \text{if $i \ne -1$ and $j = -1$} \\ a_{i-1, j-1} + ...
0
votes
1answer
23 views

Are there known patterns among minimal expressions?

Let $R = F[z_1, z_2, \dots]$ be the finite-degree polynomials in a countable number of variables. Let $\mathcal{E}(R)$ be the set of all expressions of polynomials. Note that there could be an ...
1
vote
1answer
40 views

Computational complexity of expanding a MacLaurin/Taylor Series

What methods exist to computationally determine the first $k$ coefficients of a function (possibly polynomial or rational polynomial function)? How do Mathematica/MatLab/Maple/etc. solve this ...
1
vote
3answers
33 views

How do you reckon Big-O analysis with infinite problem sets?

Let $f : X \to Y$ be a problem, for instance, $f: \Bbb{Z} \to $ a factor. Given input measure $n = |x|$, then our problem is $O(g)$ if there exists an algorithm running on a standard machine, and an ...
1
vote
0answers
52 views

My notes on $\Bbb{Z}/p\Bbb{Z}$-theoretic computational complexity

(Question at the very bottom) Def 1. Let $F = \Bbb{Z}_p$ be a finite field. Then an $F^k$-machine is a machine with $k$ input / output memory slots. All computations are done in the field $F$ and ...
1
vote
1answer
33 views

How do you define computational complexity abstractly?

Let the problem we're studying be $f : X \to Y$. Say, I don't know what I want to define time-complexity with respect to, I just know I have a map $|\cdot| : X \to \Bbb{R}$, such that $|\cdot| \geq ...
0
votes
0answers
26 views

Not every polynomial in $\Bbb{Z}_p[x]$ can be factored, but can you do next best?

If $f \in R = \Bbb{Z}_p[x]$ is irreducible or doesn't have many factors then it could be hard to compute? Possibly, I'm not saying, but... any way, what if $f = h - g$ where $h, g$ are heavily ...
0
votes
1answer
65 views

Do there exist polynomials not computable in polynomial time?

Motivation: Computing a problem in $k$ memory slots Do there exist polynomials in $R = \Bbb{Z}_p[z_1, \dots, z_k]$ that can't be computed in time polynomial in $k,p$? Thanks... Good luck! Edit. I ...
0
votes
1answer
29 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...