Problems that are not easy to solve and whose solution has market value. This implies there money to be made by presenting a solution.
- Prove or disprove P=NP, e.g. PSAT, graph isomorphism
- A million bucks goes to whoever can do it...
- Factor numbers efficiently (including in exponential time but with very small constants)
- A lot of money (or an "accident" on the freeway, courtesy of your local ThreeLetterAgency?) to whoever can do it.
- Prove or disprove that pure functional languages are a SilverBullet {Or that any paradigm is a SilverBullet, or even a brass bullet.}
- Automate boring problems so that we don't have to keep solving them
- This is constantly being done, and has been done numerous times over the past 50+ years. Trouble is, each improvement is incremental.
- Implement or define a language-neutral GUI standard that works with HTTP.
- (RemoteGuiProtocols)
- No, those are generally optimized for prototyping, not production. And, are products, not necessarily standards.
- A ProtocolIsaLanguage?. LanguageNeutral usually means little more than "using a new language that nobody likes, rather than an existing one that most people don't like).
- Implement a RelationalLanguage other than SQL
- Implementing one isn't hard; getting it accepted worldwide is the tricky part.
- Implement a MultiParadigmDatabase or DynamicRelational database.
- ProgrammingWithoutRamDiskDichotomy
- Automate testing of web applications (e.g. JavaScript menus, tricky datasets, etc.)
- Create a fast distributed database with transactional isolation
- Play a strong game of Go
- Chess was conquered by MooresLaw. Will Go eventually be conquered by:
- UnsolvableSoftwareDevelopmentProblems
I have been pondering something puzzling about text processors, along the lines of TexTheProgram. It is tough to assign forward page number references until you have processed the whole book. But, what if the page number on say page 50 causes the page to "bump up" to the next page, changing the very reference that it bumped? For example page 50 could say "see page 99 for more details". But, putting "99" there bumps up the page count such that now the target is page 100 instead of 99? It may not be common enough to worry about in practice, but I see the potential for an infinitely loop. I suppose the text processor could assume large page number references, and then pad line or paragraph spacing to make up for the overestimates.
A: WhiteOut ;-)
The loop isn't infinite. It's worst-case runtime is log(n) where n is the number of page references; however in practice the runtime doesn't exceed 2.
See also: ResearchIdeas?
Interesting Problems