Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

1
vote
0answers
30 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...
0
votes
0answers
16 views

How to determine sub-exponential time growth?

I'm a little bit confused of sub-exponential time growth; consider the definition from Hoffstein's book An Introduction to Mathematical Cryptography: Given input of $k$ bits, then if an algorithm ...
0
votes
0answers
36 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
2
votes
0answers
22 views

Complexity of finding extremal rays

Suppose that $\{L_i\}$ is a collection of $k$ linear forms on $\mathbf R^n$. Let $$C=\{x \in \mathbf R^n : L_i \cdot x \geq 0 \text { for all } i \}$$ be the closed convex cone defined by the ...
1
vote
0answers
50 views

If $P=NP$, prove that $L' \in NP$

I think I'm overthinking this problem and need some hints in the right direction. The goal of this question is to show that if $P=NP$ then for every language $L \in NP$ via a polynomial time verifier ...
0
votes
1answer
39 views

Order functions by speed of their asymptotic growths

We are given list of functions. Task is to sort it by the speed of their asumptotic growth in ascending order. Yes, it's a homework. I already spent some solid amount of time calculating limits. I ...
0
votes
0answers
12 views

Proof of theorem about connection between nondeterministic and deterministic Turing machines complexity classes

I need source for proof of this theorem: Every $T(n)$ time nondeterministic Turing machine has an equivalent $2^{O(T(n))}$ deterministic Turing machine. I have book by Michel Sipser, ...
0
votes
0answers
28 views

Prove that THEOREMS is NP-complete

I have an essay where I shall explain polynomial time reductions, NP definitions and give an "non-strict" proof that THEOREMS is NP-complete. THEOREMS is the problem of providing mathematical proofs ...
0
votes
2answers
62 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
65 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
64 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
50 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
43 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
19 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
109 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
67 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
74 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
28 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
48 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
46 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
399 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
19 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
35 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
41 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
696 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
89 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
23 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
61 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
48 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
936 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
33 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
14 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
26 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
46 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
93 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
27 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
35 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 ...