Are There Any Problems That Cannot Be Solved in Linear Time?

  • Context: Undergrad 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around identifying problems that are suspected of not having linear-time solutions, with a focus on computational complexity and algorithmic efficiency. Participants explore various examples and classifications of problems, including those in polynomial time and NP-complete categories.

Discussion Character

  • Debate/contested, Technical explanation

Main Points Raised

  • One participant requests a list of problems suspected of lacking linear-time solutions, mentioning multiplication and sorting as examples.
  • Another participant cites NP-complete problems, including factoring a number and finding the shortest path for a traveling salesman, as examples of problems that may not have linear-time solutions.
  • A later post clarifies that the focus is on polynomial-time problems rather than NP-complete ones.
  • Additional examples of problems suspected of not having linear-time solutions include the Fast Fourier Transform (2D or 3D), calculating most trigonometric functions to specified precision, finding the first "n" primes, and defragmenting a disk with "n" fragments.
  • One participant notes that counting to "n" could also be problematic due to the need for longer word lengths as "n" increases.

Areas of Agreement / Disagreement

Participants express differing views on which problems fall under the category of not having linear-time solutions, indicating that multiple competing views remain on the topic.

Contextual Notes

Some assumptions about problem classifications and definitions of linear-time solutions may be missing, and the discussion does not resolve the complexities involved in categorizing these problems.

Dragonfall
Messages
1,023
Reaction score
5
Can I have a list of problems suspected of not having linear-time solutions? Like multiplication and sorting.
 
Mathematics news on Phys.org
I meant a poly-time problem.
 
Fast Fourier transform (2d or 3d).
Most trigonometric functions to any specified precision.
Finding the first "n" primes.
Defragmenting a disk with "n" fragments.

Technically, counting to "n" because eventually you would need longer and longer word-lengths.
 

Similar threads

High School A symmetric problem has an asymmetric solution - why?
  • · Replies 21 ·
Replies
21
Views
3K
Undergrad How do you solve systems of equations in complex physics problems?
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Where in STEM can I expect to use dual basis, dual map, annihilator?
  • · Replies 2 ·
Replies
2
Views
1K
MHB Communication in mathematics and physics
  • · Replies 1 ·
Replies
1
Views
2K
High School Are Inverse Problems More Complex Than Direct Problems in Mathematics?
  • · Replies 13 ·
Replies
13
Views
3K
High School Can Multiple Outputs from a Single Input Help in Constructing Non-Linear Curves?
  • · Replies 7 ·
Replies
7
Views
2K
High School English Translation of Italian Lecture Notes: Equations & Solutions
  • · Replies 11 ·
Replies
11
Views
2K
Undergrad Optimization problem with multiple outputs: impossible?
  • · Replies 6 ·
Replies
6
Views
3K
High School What unique contributions to math did linear algebra make?
  • · Replies 19 ·
Replies
19
Views
4K
High School Relation between Division and multiplication
  • · Replies 50 ·
2
Replies
50
Views
5K