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)

0
votes
1answer
184 views

Looking for a Set generator

English is not my native language. Hello everybody. If I have a finite set of natural numbers. It is always possible to find an algorithm that generates it (and of course not the trivial one that ...
6
votes
1answer
816 views

How to find an expression whose value is 190

Given a set of numbers (in this case): 3, 7, 7, 100, 50 Either: prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + ...
2
votes
1answer
339 views

How to get the bounds of exponential function

I have this function $(\frac{d}{d+1})^d$. How can I get the lower and upper bound of this function
1
vote
1answer
903 views

Greedy Optimized Subset-Sum Problem

Given positive integers $a_1,...,a_n,b$, find $x_1,...,x_n \in \{0,1\}$ such that $a_1x_1 + ... + a_nx_n \lt b$ but is as large as possible. How do I show that there is a greedy algorithm to this ...
1
vote
1answer
40 views

Prove that for n~=n' sum is much smaller than the case with n=n'

Hi I want to prove that this summation is much smaller for $n\neq n'$ than for the case where $n=n'$. I have seen this fact with simulation results. But I don't know how to prove it in mathematics. ...
-1
votes
1answer
142 views

what is a closure (hull) operator?

Just that. what is a closure operator? reading the wiki wasn't enough and i would like to know more. I'd be happy if someone shared examples of closure operators so that i may further understand ...
8
votes
2answers
109 views

Can the rank of the homology group of an abstract simplicial complex be computed in polynomial time?

I want to write a function that does the following: Input: An integer $n$ A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets ...
1
vote
1answer
471 views

how discrete mathematics is related to computerscience

I have this basic question for sometime since i came across discrete mathematics, hence this question. How discrete mathematics is related to computer science. How its notions are used in the field of ...
1
vote
1answer
290 views

How to deduce the psition mapping of entries of a matrix?

I would be thankful if any peer shed light on me. Assume that the mapping of a set is unknown. By knowing n number of E element sets and the transformed sets with positioned elements, How can I ...
0
votes
0answers
65 views

Complexity of index calculus method

I read somewhere that complexity of index calculus method which calculates discrete logarithm over $Z_p^*$ is $O\left(e^{(1 + o(1))(\sqrt{ln(p)\times ln(ln(p))}\;)}\right)$. My question is, why ...
1
vote
0answers
72 views

Is discrete ultralogarithm harder than discrete logarithm?

Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing $g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
2
votes
2answers
62 views

Question about what it means to be in “NP”

Suppose I am trying to prove language $L$ is in NP. Does it suffice to construct a nondeterministic Turing machine that accepts all strings in the language in polynomial time? Or must the machine ...
0
votes
0answers
124 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
2answers
102 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
0
votes
1answer
69 views

efficiency of verifier of Boolean

For a Boolean expression formula φ, For a binary literal $i∈(0, 1)^l $ V(φ,i) is an Turing algorithm which decides whether i satisfies φ or not ...
1
vote
1answer
47 views

Denesting Logarithmic expressions

$\log_7(\log_2(3)) + \log_7(\log_5(6)) + \log_7(\log_{11}(1/2)) = \log_7(-1) + \log_7(\log_5(3)) + \log_7(\log_{11}(6))$ This can only be simplified by using the sum to product rule and noticing that ...
10
votes
3answers
300 views

Why isn't NP = coNP?

Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
6
votes
2answers
3k views

Minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
0
votes
1answer
443 views

Proving By reduction from the Halting Problem

I want to solve the following exercise in Computability and Complexity Theory: By providing a reduction from the HALTING problem to REACHABLE-CODE, prove that REACHABLE-CODE is undecidable. ...
2
votes
1answer
104 views

knapsack with only odd elements

Is it feasible to solve the subset sum problem if all the elements are odd and we also know that whether odd or even no. of elements are used to form the sum for example - If i have the set -{ 9, 13 , ...
2
votes
2answers
611 views

transform traveling salesman problem into subgraph isomorphism problem

Lets say, I could solve subgraph isomorphism problem in constant time. How could I use this to solve traveling salesman problem? aka... how to transform traveling salesman problem into subgraph ...
2
votes
1answer
139 views

Big $\mathcal{O}$ notation for multiple parameters?

The following is an excerpt from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (aka CLRS): $\mathcal{O}(g(n,m)) = \{ f(n,m): ...
2
votes
0answers
93 views

Solving recurrence relation of algorithm complexity?

Supposing I write an algorithm that results into this kind of recurrence relation $$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
1
vote
0answers
83 views

Expansion in powers

Let $n=2k, k \in Z_+$. Let $$P_k\left(\frac{t}{\sqrt n}\right)=n!\sum_{\begin{smallmatrix} n_1+\ldots+n_k=n \\ ...
0
votes
1answer
129 views

understing Cook theorem and input length

Following is my understanding of Cook theorem. Let P be a $\mathcal{NP}$ problem. And let M be a polynomial NDTM for P, $$ M(x) = \left\{ \begin{array}{ll} 1\text{ if x∈ P}\\ 0\text{ ...
3
votes
1answer
1k views

Proving that a function is negligible

In mathematics, a negligible function is a function $\mu(x):\mathbb{N}{\rightarrow}\mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $x > N_c$, ...
1
vote
1answer
167 views

Restricted partitions?

Suppose I have an integer N and i want to partition it, it must only involve numbers in set $S$ and the number should appear only once. For example if $N = 12$ and $S = \{3, 5, 7\}$ the answer should ...
0
votes
1answer
773 views

Solving a recurrence relation using Z transform

I'm trying to solve the following recurrence using Z transforms: For $n\in \mathbb{N}^{*}$ $T(n)=1\ for\ n< 4$ $T(n)=T(\lfloor \frac{n}{4} \rfloor)+T(\lfloor \frac{3n}{4} \rfloor)+n\ for\ n\geq ...
3
votes
2answers
131 views

Would it be possible to concoct a “harmful” axiom?

Suppose I run an automated theorem prover. It begins with the axioms of ZFC, and using a random number generator, it proves more theorems, and it runs for two days. At the end of the second day, it ...
3
votes
1answer
75 views

Computing the period of a fraction polynomial in the number of digits

So I have a fraction a/b that is known to be repeating. How do I compute the period of the repeating decimal in polynomial-time in the number of digits of A and B?
6
votes
1answer
136 views

Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
0
votes
1answer
266 views

algorithm and Cook theorem

Let $A$ be a set of decision algorithms which are running in polynomial time and which takes natural numbers as inputs. $x\in A$ if and only if for $i\in N$ $x(i)=0$ or $x(i)=1$ ...
0
votes
1answer
223 views

About Cook–Levin theorem

I want to check whether I understand the Cook-Levin theorem fully (using the Travelling Salesman Problem as an example). Given a weighted graph $G$ and an number $L$, the a Travelling Salesman ...
1
vote
2answers
60 views

Confusion related to P and NP problems

I have this confusion related to P and NP problems. Why is P a subset of NP? I didn't get it. P problems can be solved in polynomial time. However, NP problems cannot but only verify if a solution is ...
1
vote
2answers
2k views

What does it mean for a function to be polynomially bounded

There is a definition in my notes and says, When functions are polynomially bounded, the initial conditions (the value on small inputs) do not make a difference for the solution in ...
2
votes
1answer
162 views

Games for which the Lemke-Howson algorithm provides incomplete results

I am exploring a large number of 2-player games. The Lemke-Howson algorithm is computationally very reasonable, and is able to find many equilibria. On the other hand, I know that there are equilibria ...
1
vote
1answer
415 views

Well formed formulas of all mathematical proof

Last week, I asked the "automated proof-checking machine." Many answered that automated proof-checking machine already exists in first-order theory. However I have still question. For the operation ...
0
votes
1answer
128 views

Array resize problem

I need help with this problem if anyone can help. Suppose you have an empty array of size $s$. Then you keep inserting elements in it. But before you insert an element, if the array is filled, then ...
0
votes
1answer
41 views

Resizing array problem

I need some help with this problem. Suppose you have an array of size $n$ where $n = 4^i$ for some $i \geq 0$, with initially $n$ elements in it. Let $m$ be the current number of elements in the ...
2
votes
2answers
445 views

Automated proof-checking machine

In the future, theoretically, is it possible to make an automated proof-checking machine? It means, given mathematical axioms and definitions, the computer can decide that a proof is correct or not, ...
0
votes
1answer
191 views

Solving the following recurrence relation

I have a recurrence relation, it is like the following: $$ T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm} $$ To solve this and find a Θ bound, i tried the following: I ...
1
vote
2answers
115 views

The use of master theorem appriopriately

I have a recurrence relation and trying to use master theorem to solve it. The recurrene relation is: $$T(n) = 3T\left(\tfrac n5\right) + \sqrt n$$ Can i use the master theorem in that relation? If ...
1
vote
2answers
73 views

Sequences and Languages

Let $U$ be the following language. A string $s$ is in $U$ if it can be written as: $s = 1^{a_1}01^{a_2}0 ... 1^{a_n}01^b$, where $a_1,..., a_n$ are positive integers such that there is a 0-1 ...
2
votes
1answer
91 views

How is naive CLIQUE algorithm polynomial time?

I am reading Introduction to Algorithms 3rd for my CS course. Just before theorem 34.11 on pg 1087, it says the running time of the naive algorithm to try all k-subsets of $V$ is ...
4
votes
2answers
95 views

How to recover a shuffled matrix

Suppose that I have a matrix $A$. $A$ can be a rating matrix. That is, $A(i,j)$ is the rating user $i$ has given to item $j$. Suppose that I shuffle the rows and columns of matrix $A$ and get ...
2
votes
1answer
61 views

What's the relationship between the Ham Sandwich Theorem and the PPAD Complexity Class?

Wiki says: "The Ham sandwich theorem is known to lie in PPAD but it remains an open question as to whether or not it is PPAD-complete." What is the computational problem based on the Ham Sandwich ...
2
votes
2answers
3k views

Time complexity of a modulo operation

I am trying to prove that if $p$ is a decimal number having $m$ digits, then $p \bmod q$ can be performed in time $O(m)$ (at least theoretically), if $q$ is a prime number. How do I go about this? A ...
1
vote
2answers
1k views

Solving a recurrence relation using master method

I know that the Master theorem is used for the recurrence relations of the form: $$T(n) = aT(n/b) + f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master ...
1
vote
2answers
312 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
3
votes
0answers
199 views

$\sum _{i=1}^{n} \sum _{j=1}^{n} \sum _{k=1}^{n}\sum _{l=1}^{n} A(i,j)A(i,k)A(i,l)A(j,k)A(j,l)A(k,l) $

I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum _{i=1}^{n} \sum _{j=1}^{n} \sum_{k=1}^{n} A(i,j)A(j,k)A(k,i)$, where A(i,j) is the a ...