Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

0
votes
2answers
56 views

What does psuedo-polynomial algorithm for subset sum problem mean?

Help me out here - just trying to better understand what 'psuedo-polynomial' means... If the input to an NP-Complete problem is 100 items(ie n=100), and the 'target' is the actual value '100'(t=100): ...
2
votes
1answer
62 views

Prove 2-HamiltonianCycle $\in \textbf{NP}$

Just want to verify that I have the right idea here with this hamiltonian cycle question. $HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex ...
1
vote
2answers
63 views

Implication of P =NP on video games?

I was wondering if NP problems were actually solvable in P time, then what will be the impact on Video Games, if any ?
1
vote
0answers
49 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
3
votes
0answers
30 views

Examples of functions which grow faster than their computational complexity.

A good example of this would be the function $f$ defined as follows, $f(n) = (10^n-1)$. While in this form it's equation is exponential, it is easy to note that $$f(n) = 99...9 \,(n \text{ times}).$$ ...
1
vote
1answer
38 views

Decidability of normal modal logics

Let's say we have systems of modal logic defined as smallest sets containing propositional tautologies, all instances of schema $\square F \to (\square(F \to G) \to \square G)$ all instances of ...
1
vote
2answers
28 views

exponential time complexity

given that: $f(n) = a^n$ and $g(n) = b^n$ where, a,b are positive integers and n is a positive real number does there exist some $f(n) \notin \mathcal{O}g(n)$? ie. $f(n) \leq c_1 \cdot g(n)$ is ...
2
votes
0answers
17 views

A confusion about RP class of problems

I have some notes which introduces the quantifier $\exists^+x$ and interprets it as "the overwhelming majority of $x$". Then, it defines RP (Randomized Polynomial) as: $$ L\in RP\Leftrightarrow ...
0
votes
0answers
81 views

Prove that div(x,y) is primitive recursive (integer division

Prove that div(x,y) is primitive recursive (integer division). I tried thinking about it, I just don't know how to write it formally. it is kinda obvious that I should subtract y from x several times ...
1
vote
1answer
39 views

Why one defines the proper complexity functions?

Definition: A proper complexity function is a function $f$ mapping a natural number to a natural number such that: $f$ is nondecreasing There exists a $k$-string Turing machine $M$ such that on any ...
3
votes
1answer
111 views

Minimizing Height of a Table

This optimization question popped into my mind while working with latex tables: Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ ...
2
votes
2answers
58 views

What is the Big O complexity of this equation?

$$\frac{n+1}{2}(\log_2(n-1))+\frac{n+1}{2}-\log_2(1)-\log_2(3)-\dots-\log_2(n)$$ What is the Big O complexity of this equation? My initial guess is $n \log(n)$ But after a calculation, I ...
1
vote
1answer
69 views

The complexity of counting solutions to $x_1 + \dots + x_m = N$ in non-negative integers under constraints

Consider the equation $$x_1 + \dots + x_m = N$$ where $x_1,\dots,x_m \ge 0$ and under the additional constraints $x_k \le a_k$ for $k=1,2,\dots,m$. I'm interested in knowing whether the number of ...
0
votes
0answers
26 views

Why $17T(n/16) + n \log n$ satisfies the case 2 of the Master Theorem?

Using the Master Theorem, we have that $17T(n/16) + n \log n$ is $\theta(n^{log_{16}17} log^2 n)$ My question is, why $n \log n = \theta(n^{\log_{16}17} \log^1 n)$, being $\log_{16}17$ approximately ...
0
votes
0answers
12 views

Complexity Multiplication Matrix-Vector in binary

I'm calculating the complexity of certain algorithm and I need know What's the complexity of the best algorithm, without parallel, to calculate the matrix vector multiplication over GF(2)?. The ...
0
votes
0answers
44 views

How to convert a subgraph isomorphism problem to subset sum problem

Let's say you want to solve a subgraph isomorphism problem using a subset sum solver. What would be the right steps to convert SGI to SS?
0
votes
1answer
40 views

Switching edges and vertices

I am attempting to convert the problem of finding an edge dominating set into a dominating set. I need a way to change the edges of a graph to the vertices and the vertices of a graph to the edges, ...
4
votes
3answers
381 views

Growth rate of $n^{\sin n}$

Is there a way of comparing the growth of functions $ f(n) = n ^ {\sin(n)} $ and $ g(n) = n ^ {1/2} $ in terms of $ O, o, \Omega, \omega, \Theta $ ? Periodically, $ f(n) $ keeps going above and ...
0
votes
2answers
18 views

Lowering the start indexes in sums

I'm implementing a CYK algorithm in my software and I've found a pseudo-code on Wikipedia. Here's its complexity(modified version for special use, which doesn't go from ...
0
votes
0answers
43 views

What is the complexity of computing some problems related to real analysis

I was thinking. I do not know whether my question has any sense. I want to know is there any way to compute analytically or explicitly some of the problems give below. What is the complexity of ...
1
vote
1answer
32 views

problem about computational complexity

Exercise: Prove that the computational complexity of the binomial coefficient \begin{equation*} \binom{m}{n} \end{equation*} is O($m^{2}$$\log^{2}n$). using the fact that the computanional ...
0
votes
0answers
33 views

What is the space complexity of inverting a real valued sparse banded diagonal symmetric matrix?

Of course, when I say ``inverse'' what I really mean is solving a system of equations $Ax=b$ where $A$ is sparse, banded diagonal, symmetric, real valued $N \times N$ with a bandwidth of $k$. I know ...
1
vote
0answers
40 views

What makes the permanent lot more difficult than the determinant

The permanent of an $n$-by-$n$ matrix $A$ = $(a_{i,j})$ is defined as: $\operatorname{perm}(A)=\sum\limits_{\sigma\in S_n}\prod\limits_{i=1}^n a_{i,\sigma(i)}$. ...
6
votes
1answer
678 views

Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
3
votes
2answers
77 views

Big O/little o true/false

These are all from Sipser's book, second edition. I was just hoping someone could verify/explain those that are more difficult for me. $2n = O(n)$: true $n^2 = O(n)$: false $n^2 = O(n\log^2 n)$: I ...
0
votes
0answers
14 views

In the definition of NP, is it required to have polynomially bounded length of certificate?

So given the definition in our lectures, we were told that NP is defined as the set of languages $L$ s.t. there exist a polynomial time bounded Turing-acceptor M s.t. $L ={w: M accepts(w#c) for some ...
3
votes
2answers
21 views

How to figure out the time complexity for an algorithm with dynamic input parameters?

I have an algorithm that depending on the length of the input array and its values could take more or less operations to complete, for example, for a set with some length it could take 10.000 ...
2
votes
1answer
60 views

From programming to mathematics

I'm studying algorithms design and analysis, but there is a code that I can't understand. I know that: Let $\mathcal P$ be the main program, and $\mathcal P \in O\left(\varphi(n)\right)$ with ...
0
votes
0answers
46 views

Prove that $EXP^{EXP}\neq EXP$

I have to prove that $EXP^{EXP}\neq EXP$. $$EXP=EXPTIME$$ $EXP^{EXP}$ is all the languages which can be solved by turing machine with oracle calls (which solves language in $EXP$) in $EXP$ time. I've ...
11
votes
1answer
924 views

Minimum number of different clues in a Sudoku

I wonder if there are proper $9\times9$ Sudokus having $7$ or less different clues. I know that $17$ is the minimum number of clues. In most Sudokus there are $1$ to $4$ clues of every number. ...
1
vote
1answer
39 views

Complexity of primenumber test

The german wiki claims that the approach to check if any number before p is a divisor of p is a polynomial time algoritm. I dont understand this claim. Because imho this is linear, which is polynomial ...
0
votes
2answers
32 views

Sum of a sum [algorithm design and analysis]

I'm studying the algorithm analysis of one piece of code, and I have to find the big-O notation of the sum of a sum. ...
0
votes
0answers
13 views

What are the current lower bounds for $NTIME$ vs $DTIME$?

Trivially, we have $DTIME(f(n)) \subset NTIME(f(n))$. Is it known whether or not this inclusion is strict? Do we know if $DTIME(f^c(n)) \subset NTIME(f(n))$ for any $c$? Is there any $c$ for which ...
0
votes
1answer
50 views

Is there a limit for how “good” a numerical method can be?

Multiplying two matrices $A \cdot B$ of size $n \times n$ in the trivial way requires $n^3$ computations. However, more efficient algorithms such as the Strassen algorithm have a lower complexity of ...
0
votes
1answer
17 views

Understanding the meaning of the Linear speedup

The linear speedup theorem informally says the following thing: If $M$ is a Turing machine that operates with time $f(n)$ to do a certain task on some input $x$ then for every $\epsilon>0$ we can ...
2
votes
3answers
44 views

Help making the distinction between polynomial and exponential time

I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = $\{\langle G,s,t \rangle | G$ is a directed ...
0
votes
0answers
16 views

Any problems that reduces to shortest path?

I am writing an introduction to complexity theory, and in my first chapter I discuss polynomial-time algorithms with language theory and shortest path as an example problem. My professor wanted me to ...
0
votes
1answer
88 views

If the union of two languages is NP-complete, is one of them NP-complete?

Question 1) If $A\cup B$ is NP-complete, and $A$ is NP, and $B$ is P, then is $A$ NP-complete? I don't think so but I am unsure. When I try to reduce $A\cup B$ to $A$, I fail because strings in $B$ ...
0
votes
1answer
23 views

What is the sum of recursive logarithms?

I am trying to deduce the complexity of a rather odd algorithm. I have got it down to this form: $$ O(n \times (\sqrt n)^2 + n \times (\lg \sqrt n)^2 + n \times (\lg \lg \sqrt n)^2 + \space ... + ...
0
votes
0answers
27 views

Why is integer programming in fixed dimension easier than in general?

When the dimension is an a priori fixed constant, then integer programming feasibility (the existence of an integer point in a polyhedron) can be decided in polynomial time. If the dimension is not ...
0
votes
1answer
41 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
0
votes
1answer
33 views

3-SAT vs P/poly

Why is the circuit for a 3-SAT instance not polynomial in size? That is, when I am converting a SAT formula into a circuit, isn't the size of the circuit polynomial, as I have polynomial number of ...
0
votes
1answer
50 views

Find whether $f(n) = O(g(n))$, $f(n) = \Omega(g(n))$ or $f(n) = \Theta(g(n))$ if $f(n) = n^\frac{1+\sin(\frac{n\pi}{2})}{2}$ and $g(n) = \sqrt{n}$.

Find whether $f(n) = O(g(n))$, $f(n) = \Omega(g(n))$ or $f(n) = \Theta(g(n))$ if $f(n) = n^{\big(\displaystyle 1+\sin({n\pi}/{2})\big)/2}$ and $g(n) = \sqrt{n}$. I tried plotting this out - it ...
0
votes
0answers
20 views

Complexity of Cartesian product involving multiple set

I want to evaluate complexity of Cartesian Product involving N sets, each of N set as subset of super set having 2E elements ( actually E distinct elements, each repeated twice ), Repetition of ...
2
votes
1answer
34 views

Max Word Size as a Function of Number of Words

I want to describe the relationship between largest word length, l, and the number of words in a set, n. Example: For the set ...
0
votes
3answers
61 views

How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number

Given: $$ X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1} $$ $$ z \in \mathbb N $$ Wanted result: $$ Y = \left\{ y_1, y_2, \ldots , y_n ...
0
votes
1answer
80 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
0
votes
1answer
33 views

Natural Decision Problem not in PTIME

Are there any natural decision problems which are guaranteed not to be in $\mathsf{PTIME}$? Preferably natural graph problems like $\mathsf{CLIQUE}, \mathsf{VERTEXCOVER}$ etc. (However, they would be ...
1
vote
2answers
51 views

Proof of a lemma with inequalities

I read a paper about keyword search and just cannot understand the lemma. Please help me to understand it, thanks. Lemma 1: Let $v_1,v_2,\ldots,v_r$ be $r$ non-descending integers in the range from ...
0
votes
0answers
17 views

Reduction of halting problem

I can show that this reduction !H ≤ H where H is the general halting problem an !H is the complement of it. But what with H ≤ !H ...