Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

0
votes
1answer
28 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
4 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 ...
1
vote
0answers
11 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.
1
vote
2answers
46 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
17 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
17 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
24 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
62 views

Necessary and sufficient conditions for $\rm P \neq NP$ maybe?

Please review the $\rm P \neq NP$ problem here. I'm working on an algebraic approach to this problem, and all my notes are currently here. Conjecture 1 For all $f \in F[x_1, \dots, x_k]$, a minimal ...
0
votes
0answers
38 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
29 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
9 views

calculating input size of extreme point for polyhedra

Conside the nonempty polyhedral set $F=\{x\in\mathbb{R}^n|Ax=b,x\ge > 0\}$, where $A\in\mathbb{Z}^{m\times n}$ and $b\in Z^m$ take integer values. Let $$a_1=\max_{ij}\{|a_{ij}|\}\hspace{0.1in} ...
0
votes
0answers
23 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
51 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
22 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$, ...
-2
votes
1answer
23 views

travelling salesman problem approximation [on hold]

Consider the symmetric travelling salesman problem $\Delta TSP$: An instance consists of a complete undirected graph $G$ (all possible edges are present), a nonnegative integer cost $c_{ij}=c_{ji}$ ...
0
votes
1answer
19 views

circuits complexity

I ran into this claim and I dont really understand why it is true ( and I need to use it for proving other things) Every function from $(0, 1)^n$ to $(0, 1)$ is computable by a $2^n10n$-sized ...
0
votes
1answer
22 views

Is there a way to compute if(i < j) k := (a + b)c with polynomials over $\Bbb{Z}_p$?

Let $p$ be a prime and let all variables be in $\Bbb{Z}_p$. Then you can write the result of if(i > 0) k = (a + b)c; (C code) as a polynomial $k := ...
0
votes
0answers
11 views

Are these computational models equivalent?

Let $f : X \to Y$ be a problem that you want to compute. Say we have an $O(1)$-computable maps, $\phi, \psi$, such that $X \xrightarrow{\phi} (\Bbb{Z}_n)^k \xrightarrow{\psi} Y$. After all, ...
0
votes
1answer
45 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
2
votes
0answers
26 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
1
vote
0answers
27 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
13 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
20 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
18 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
40 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
13 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
9 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
27 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
35 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
58 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
57 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
38 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
27 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
31 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
16 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
15 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
18 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
33 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
108 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
51 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
68 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
24 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
10 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
25 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?
-1
votes
0answers
29 views

How To Solve the recursion?

Need help with the following recursion: $$T(n)=2T\left(\frac n2\right)+ \frac n{\log n} $$ I Tried to solve it to no avail, and the master theorem doesn't seem to work on it. Thanks
-1
votes
0answers
14 views

NP has oracle $\Sigma_k \cap \Pi_k$

Can someone show the prove why: $NP^{\Sigma_k \cap \Pi_k} = \Sigma_k$?
0
votes
1answer
29 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
368 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
15 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
41 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 ...