Computer Science problems

Classification of various types of Computer Science Problems

Page 1 of 1

2 Replies - 5612 Views - Last Post: 03 May 2010 - 09:43 AM Rate Topic: -----

#1 singularity  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 17
  • View blog
  • Posts: 184
  • Joined: 17-October 08

Computer Science problems

Posted 19 April 2010 - 06:25 AM

Computer Science Problems are mainly categorized into the types of complexities involved in solving them. Yes I am talking about Big Oh Notations and all that. But this tutorial will not focus into Big Oh Notation rather it gives a general idea about the various types of problems in Computer Sciences with a special emphasis on NP Complete Problems(hey I will explain below what is NP Complete).

As a brief review, we first discuss the different categories of functions for big-O notation:

The ones that involve n as an exponent (n! or nn) are called exponential functions. Functions whose growth is <= nc for some relatively small constant c are polynomial functions. Linear functions have growth proportional to n. Sub-linear functions have growth proportional to log n. A constant time function has growth independent of n

These descriptions of functions are frequently used to characterize different sets of problems. The general categories are:

Intractable or Exponential time problems: These are problems that require exponential time. Moreover, it has been proven that a solution in less than exponential time is impossible. For example, consider the problem of listing all possible committees of size one or more that could be formed from a group of n people. There are 2n - 1 such committees so any algorithm that solves this problem must have at least 2n - 1 steps, and thus a running time proportional to 2n. This problem cannot possibly have a polynomial solution.

Polynomial Time Problems: These are problems for which sub-linear, linear or polynomial solutions exist. Insertion sort, quicksort, mergesort and other sorting algorithms are good examples, as well as finding the smallest or largest values in a list. Any algorithm whose running time grows proportional to a polynomial function can solve reasonable-size problems if the constant in the exponent is small.

NP-Complete: No polynomial solution has been found, although exponential solutions exist. However, it has not been proven that a polynomial solution could not be found.

Some famous examples:

1) Traveling Salesperson (TSP): Given a map of cities and a cost of travel for each pair of cities, is it possible to visit each city exactly once and return home for less than k bucks?

2) n-bookshelf packing: You are given k books to put on n shelves. Will they fit? (the books are all of different sizes).

This group of problems is very interesting for a number of reasons. First of all, the "NP" means "nondeterministic polynomial". Nondeterministic does not mean that we have not yet been able to determine if the problem is polynomial. It means that the algorithm that we might define to solve one of these problems is non-deterministic, i.e., there is an element of chance in the algorithm. For example, we might write a solution as follows for the Traveling Salesperson problem:
Choose one of the possible paths, and compute its total cost.
If this cost is no greater than the allowable cost,
	then declare a success
	else declare nothing.



Someone must choose one of the possible paths (this is the nondeterministic part). If we choose the right one, the problem is solved quickly; if not, we learn nothing. We define the running time of an NP algorithm as the time required to execute the algorithm if we make the "right" choice, meaning the choice that would lead to a solution in the optimal amount of time. So we are trying to measure how good the algorithm is, not how good our choices are.

According to this definition, the Traveling Salesperson problem has a polynomial solution. If we make the right choice, we just have to compute the distance for n cities which is proportional to n.

Of course, the class of NP problems includes the truly polynomial problems. If we can design a deterministic (no choices) polynomial solution for a problem, then we surely can design a nondeterministic one. In addition, the Traveling Salesperson problem suggests that there might be NP problems that do not have polynomial solutions. In other words, there appear to be problems that can be solved in polynomial time by nondeterministic algorithms, but that might require exponential time by a deterministic algorithm. But no one has been able to prove this. In particular, no one has been able to show that there does not exist a polynomial solution to the Traveling Salesperson problem. This is still one of the open questions in theoretical computer science (but most computer scientists are of the opinion that a polynomial solution does not exist for TSP).


Characteristics of NP-Complete Problems

In general the NP Complete Problems exhibit the following characteristics:

• Each problem is solvable, and a relatively simple approach solves it (although the approach may be very time-consuming). For each of them, we can simply enumerate all the possibilities, all ways of assigning the logical values of n variables, all subsets of the set S. If there is a solution, it will appear in the enumeration; if not, we will discover this as well.
• There are 2n cases to consider if we use the enumeration approach. Each possibility can be tested in a relatively small amount of time, so the time to test all possibilities and answer “yes” or “no” is proportional to 2n.
• The problems are apparently unrelated coming from logic, number theory, graph theory, etc.
• If it were possible to guess perfectly, we could solve each problem in a very small amount of time. The verification process could be done in polynomial time, given a good guess.


This concludes my first tutorial here at DIC, I hope you enjoy it and found it useful. I am looking to further expand it as and when I get the time. Make sure to post a comment as your feedback.

Cheers!!





Is This A Good Question/Topic? 2
  • +

Replies To: Computer Science problems

#2 motcom  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 290
  • View blog
  • Posts: 1,371
  • Joined: 16-June 08

Re: Computer Science problems

Posted 23 April 2010 - 12:39 PM

@singularity - this is what i can't explain in detail like you did but i find total truth in your explanation - good one...
Was This Post Helpful? 0
  • +
  • -

#3 singularity  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 17
  • View blog
  • Posts: 184
  • Joined: 17-October 08

Re: Computer Science problems

Posted 03 May 2010 - 09:43 AM

View Postmotcom, on 23 April 2010 - 06:39 PM, said:

@singularity - this is what i can't explain in detail like you did but i find total truth in your explanation - good one...


Thanks, I am looking to expand it. Hopefully you can learn more from there. I would PM you when I come with the next one!!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1