# THEORY OF COMPUTATION - COMPUTATIONAL COMPLEXITY

Computational Complexity Homework for a Theory of Computation Course.

Nice opportunity to raise your **CODER RATING** !

[url removed, login to view] that the language L = {udu|u is a member of {a,b} can be decided by a Turing machine M with the running time tM(w)=c * |w|^2 for some constant c.

[url removed, login to view] problems a,b,c,and d, formulate each computational problem in the form of a language. For every language, show that it is *NP* (decribe a polynomial-time verification algorithm for the language). For every language, briefly describe a deterministic algorithm deciding it.

a)The **Partition Problem** is: Given a finite set of integers S={a1,a2....,an}, determine if the set can be partitioned into two sets S1,S2 such that the sum of all elements of the first set equals the sum of all elements of the second set.

b)The **Two-Machine Scheduling Problem** is : Given a finite set of integers S ={a1, a2,....,an}, partition it into two subsets S1, S2 such that the sums of elements in each set do not exceed a given bound D. (The problem relates to scheduling n tasks on two machines. Both machines have the same speed, and the order of task execution does not matter. a1,a2,....,an are execution times of the tasks. The question is, if we have deadline D, determine if all tasks can be distributed between two machines so that all of them can be completed before the deadline).

c)Let G=(V,E) be an undirected graph. A set V' subset V of nodes is called a cover of the graph G if every edge in G is incident to at least one vertex in V'. The **Node Cover Problem** is, given a graph G and a number k>1, determine if there exists a cover C of the graph G such that |C| <= k.

d)Let A be an m-by-n integer matrix and b be an integer m-vector. The **Integer Programming Problem** is, given such a matrix A and a vector b, determine if there exists a Boolean n-vector x (that is, x contains only 0's and 1's) such that Ax <=b.

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.

2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.

3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site).

## Platform

Word

Habilidades: ASP, Programação C, Java, Perl, PHP

( 5 comentários ) United States

ID do Projeto: #3010095

## Premiar a:

mihaiscortaru

See private message.

\$40.37 USD em 2 dias
(163 Avaliações)
6.1

## 4 freelancers estão ofertando em média \$33 para este trabalho

preyasvw

See private message.

\$42.5 USD in 2 dias
(44 Comentários)
4.7
rosoftteam

See private message.

\$5.95 USD in 2 dias
(3 Comentários)
1.4
coderinsidevw

See private message.

\$42.5 USD in 2 dias
(1 Comentário)
0.5