Smoothed Complexity Theory

Details Smoothed Complexity Theory Smoothed Complexity Theory

2012-02-09

arxiv.org/abs/1202.1936v1

Computer Science

Computational Complexity

Scientific paper

Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng (J. ACM, 2004). Classical methods like worst-case or average-case analysis have accompanying complexity classes, like P and AvgP, respectively. While worst-case or average-case analysis give us a means to talk about the running time of a particular algorithm, complexity classes allows us to talk about the inherent difficulty of problems. Smoothed analysis is a hybrid of worst-case and average-case analysis and compensates some of their drawbacks. Despite its success for the analysis of single algorithms and problems, there is no embedding of smoothed analysis into computational complexity, which is necessary to classify problems according to their intrinsic difficulty. We propose a framework for smoothed complexity theory, define the relevant classes, prove some first results, and study some examples.

Affiliated with

Also associated with

No associations

Rating

Smoothed Complexity Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Smoothed Complexity Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Smoothed Complexity Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-156654