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

Dragonfall · Jan 29, 2014

Can I have a list of problems suspected of not having linear-time solutions? Like multiplication and sorting.

.Scott · Jan 31, 2014

Any NP-complete problem such as:
factoring a number
finding the shortest path for a traveling salesman

http://en.wikipedia.org/wiki/Category:NP-complete_problems
http://en.wikipedia.org/wiki/Category:NP-hard_problems

Dragonfall · Jan 31, 2014

I meant a poly-time problem.

.Scott · Jan 31, 2014

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.

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

Discussion

Undergrad Is infinity a necessary concept?

High School Ant on a stretchy rope puzzle

High School Potato paradox

Undergrad Descartes’ Geometry of Square Roots

High School Three Squares Problem

Mathematica NDSolve with forcing function via "digital waveguide"

MATLAB Unable to produce desired results using state-space model with observer for inverted pendulum

Insights Revisiting the Velocity-Time Function

Insights Remote Operated Gate Control System

Insights AI Enriched Problem Solving

Insights Thinking Outside The Box Versus Knowing What’s In The Box

Insights Why Entangled Photon-Polarization Qubits Violate Bell’s Inequality

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

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

Discussion

Similar threads

Graduate Solving algebraic equations that cannot be solved in radicals

Undergrad Has it been proven that quintic equations cannot be solved by *any* formula?

Graduate Dark energy = cosmological constant, any problems with that?

Solving a Linear Time-Dependent Hamiltonian Problem

Graduate What are the interpretations of QM and do they have any problems?

Solve Network Programming Challenge: O(n^3) & Linear Time Solutions

Undergrad Has it been proven that quintic equations cannot be solved by any formula?