• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 01:29
CET 07:29
KST 15:29
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #235[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over1Dark completes military service, returns to SC215[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
Team Liquid Map Contest #23 Dark completes military service, returns to SC2 Weekly Cups (Nov 9-15): Clem and herO take over StarCraft open world shooter announced at BlizzCon No more SC2 streamers on team liquid?
Tourneys
Sparkling Tuna Cup - Weekly Open Tournament RSL goes to London! 2026 Offline Finals Nov 21-22 Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19) soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
BW General Discussion List of top players active on ShieldBattery NaDa's Body Shield Battery Server New Patch BGH Auto Balance -> http://bghmmr.eu/
Tourneys
SC1 Kevin Scrim hosted by SOOP (Nov 18-19) [IPSL] Winter 26-27 Round of 16! [Megathread] Daily Proleagues 2v2v2v2 Tournament Stage 2: Players
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Nintendo Switch Thread Stormgate/Frost Giant Megathread Free Space RTS Game, optimised f. Phone/Tablet etc List of Game Threads The PlayStation 5
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Trading/Investing Thread Artificial Intelligence Thread Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 8932 users

The Big Programming Thread - Page 973

Forum Index > General Forum
Post a Reply
Prev 1 971 972 973 974 975 1032 Next
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
September 25 2018 09:10 GMT
#19441
[image loading]
Time is precious. Waste it wisely.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
September 25 2018 19:11 GMT
#19442
I've discovered a solution for multiple problems that are currently considered NP hard (minimum vertex cover/perfect matching, hamiltonicity). It works for many graphs, and I have just started delving into it - I believe I may be able to extend it to a generalized solution.... or it may pretty much already be. Like I said, just started getting into it.

And yes, I am talking a solution not an approximation or heuristic.

I think I would like to go to my school, University of Maryland College Park, to get assistance with investigating this. Particularly, the math heavy side, and doing proofs. I was wondering if anyone had advice as to how I can ensure that credit for my discoveries is not taken from me, because that is not something I would like to risk.
solidbebe
Profile Blog Joined November 2010
Netherlands4921 Posts
Last Edited: 2018-09-25 19:19:10
September 25 2018 19:13 GMT
#19443
How do you mean solutions? These problems have solutions.. just not anything that runs in polynomial time as far as we know.

edit*I confused NP-hard with NP-complete.. mah bad.
That's the 2nd time in a week I've seen someone sig a quote from this GD and I have never witnessed a sig quote happen in my TL history ever before. -Najda
Simberto
Profile Blog Joined July 2010
Germany12089 Posts
September 25 2018 19:17 GMT
#19444
On September 26 2018 04:11 travis wrote:
I've discovered a solution for multiple problems that are currently considered NP hard (minimum vertex cover/perfect matching, hamiltonicity). It works for many graphs, and I have just started delving into it - I believe I may be able to extend it to a generalized solution.... or it may pretty much already be. Like I said, just started getting into it.

And yes, I am talking a solution not an approximation or heuristic.

I think I would like to go to my school, University of Maryland College Park, to get assistance with investigating this. Particularly, the math heavy side, and doing proofs. I was wondering if anyone had advice as to how I can ensure that credit for my discoveries is not taken from me, because that is not something I would like to risk.


You could do the thing where you write down the core ideas, and leave that in a closed envelope with a date on it at a notary or something.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
September 25 2018 19:18 GMT
#19445
I mean a polynomial time solution. In particular, a fairly fast one. I haven't tried to figure out the runtime yet, it's the last thing on my mind to be honest.
solidbebe
Profile Blog Joined November 2010
Netherlands4921 Posts
September 25 2018 19:24 GMT
#19446
You can also write a manuscript of your ideas and hash it and publish that hash on the bitcoin blockchain.

Just to be clear though... if you say you think you've found a polynomial time solution for NP-hard problems, then that would mean you've proved P=NP. You realize the implications here right?

Let me just say it is extremely unlikely your idea works..
That's the 2nd time in a week I've seen someone sig a quote from this GD and I have never witnessed a sig quote happen in my TL history ever before. -Najda
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
September 25 2018 21:42 GMT
#19447
well it certainly works for the graphs ive tested! but we will see how many more it will work for in the upcoming days
Acrofales
Profile Joined August 2010
Spain18502 Posts
September 25 2018 22:08 GMT
#19448
If you want to be certain, do what simberto said. A cheaper and slightly less secure way, but still very good is mailing them to yourself. Unless US Postal no longer date stamps letters, in which case it won't work. The hash is also a good idea. Doesn't really matter where you post it, as long as it's somewhere public and securely time-stamped. Hell, a blog here will probably be fine. Just never edit that post. If you want to do that, you should run it by the mods first tho.
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
September 27 2018 14:20 GMT
#19449
https://www.google.pl/search?q=db_password filetype:env

You'd be amazed...
Time is precious. Waste it wisely.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
September 27 2018 14:29 GMT
#19450
lol :/

favorite part of that is how many of those passwords are highly secure in terms of password strength. they'll never be brute forced!
Excludos
Profile Blog Joined April 2010
Norway8281 Posts
Last Edited: 2018-09-27 14:41:19
September 27 2018 14:41 GMT
#19451
Omg that is truly hilarious and sad at the same time
ZenithM
Profile Joined February 2011
France15952 Posts
Last Edited: 2018-09-27 17:17:11
September 27 2018 16:44 GMT
#19452
@travis

On the polynomial-time solution to NP-hard problems, you should note that it's easy to naturally come up with instances that are solvable by some seemingly algorithmic method efficiently. Especially for small-size instances.
Needless to say, said method would have to work on every instance no matter what. And this requires proof infinitely more than testing on some instances, as I'm sure you're aware. Edit: actually found an interesting paragraph on the idea that most instances you come up with could be "easy": https://en.m.wikipedia.org/wiki/P_versus_NP_problem#P_≠_NP ( part talking about average-case complexity)

The likelihood of you finding a general constructive solution in P (implying that P=NP) by just looking at some graphs and see that "it works" seems very small to me. And I'm definitely not saying that to make fun of you or belittle your efforts, just saying you'll have a long road (very likely fruitless) ahead of you if that's where you're at right now.

First thing I would do if I were you if you didn't already do it, is implement your solution, to the Traveling Salesman problem and test it on large instances you can find on the Internet (usually used to assess the many heuristical solutions people have come up with over the years). Short of proving anything, testing it on a large number of arbitrary complex instances might help you at least believe in yourself :D (or crush your hopes early).


Anyway if society collapses because of my guy Travis, MOM I WAS THERE, SHOUTOUT!!!
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2018-09-27 18:16:12
September 27 2018 18:15 GMT
#19453
On September 28 2018 01:44 ZenithM wrote:
@travis

On the polynomial-time solution to NP-hard problems, you should note that it's easy to naturally come up with instances that are solvable by some seemingly algorithmic method efficiently. Especially for small-size instances.

I learned that the hard way! lol
I've been doing this for a good while now, it's what I've spent the vast majority of my time on for the last year now.
I've actually thought I just about had or did have a solution several times now. Only to find out that it won't work under some condition which starts appearing more and more as the graphs grow big.

Right now I use this data set of 1001 difficult graphs: http://www.flinders.edu.au/science_engineering/csem/research/programs/flinders-hamiltonian-cycle-project/fhcpcs.cfm

I typically run mostly the smallest graphs (N=66 to ~300), because even cubic algorithms start taking up a lot of space and time when N is very high (thousands), and I want to save time during testing. I'll test in the thousands when an algorithm is optimized and I am confident in it.

This is hard for me to do much testing and development because a lot is going on in school and im trying hard not to fail while working on this. So, movement is slow.



Needless to say, said method would have to work on every instance no matter what. And this requires proof infinitely more than testing on some instances, as I'm sure you're aware. Edit: actually found an interesting paragraph on the idea that most instances you come up with could be "easy": https://en.m.wikipedia.org/wiki/P_versus_NP_problem#P_≠_NP ( part talking about average-case complexity)


Well, what I find might not work on a big set of instances because those instances need extra steps - something else has to be done. So I think a method that works for every subset under some rules is super valuable. In fact, my gut says that anything I find that is useful will likely need extra steps to handle different types of graphs.




The likelihood of you finding a general constructive solution in P (implying that P=NP) by just looking at some graphs and see that "it works" seems very small to me. And I'm definitely not saying that to make fun of you or belittle your efforts, just saying you'll have a long road (very likely fruitless) ahead of you if that's where you're at right now.


I've been on it for a while . Literally 50+ hours a week for almost every week for the last year. I can handle getting my hopes crushed repeatedly, getting my naivety stomped out.


First thing I would do if I were you if you didn't already do it, is implement your solution, to the Traveling Salesman problem and test it on large instances you can find on the Internet (usually used to assess the many heuristical solutions people have come up with over the years). Short of proving anything, testing it on a large number of arbitrary complex instances might help you at least believe in yourself :D (or crush your hopes early).


i am working on the hamiltonian cycle problem right now actually, not TSP. I do believe TSP will end up being a much more difficult problem than hamiltonian cycle.
ZenithM
Profile Joined February 2011
France15952 Posts
Last Edited: 2018-09-28 07:22:33
September 27 2018 22:47 GMT
#19454
There are probably several orders of magnitude of difficulty between finding an efficient solution to some graph instances of a specific problem, and proving P = NP (to the point where the first discovery might almost be considered worthless). But it sounds like you're at least having fun with it, committed and going in the right direction with the experiments.
Good luck!
Apom
Profile Blog Joined August 2011
France656 Posts
September 27 2018 23:29 GMT
#19455
On September 26 2018 04:11 travis wrote:
I've discovered a solution for multiple problems that are currently considered NP hard (minimum vertex cover/perfect matching, hamiltonicity).
Pro tip : you have not.

But hey, as long as you are having fun...
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
September 28 2018 08:58 GMT
#19456
Time is precious. Waste it wisely.
ZenithM
Profile Joined February 2011
France15952 Posts
September 28 2018 09:03 GMT
#19457
Legit a good movie. I remember watching it with my friends back then, it was fun. I'm guessing it would have been much worse without a CS background.
raNazUra
Profile Joined December 2012
United States10 Posts
September 28 2018 18:28 GMT
#19458
i am working on the hamiltonian cycle problem right now actually, not TSP. I do believe TSP will end up being a much more difficult problem than hamiltonian cycle.


This is a bit of a mistake. The whole point of NP-complete problems is that if you can solve one, you've solved them all. The transformation between them is already discovered. It may be circuitous, but it exists and is known.
Speak the truth, even if your voice shakes
ZenithM
Profile Joined February 2011
France15952 Posts
September 29 2018 14:58 GMT
#19459
I mean the guy is an undergrad CS student, he probably just got introduced to Complexity 101 and thought it would be cool to prove P = NP without really knowing much else. Like hundreds of students before him :D. I remember back then the professor that was teaching us complexity theory told us he regularly received "proofs" of P vs NP and couldn't bother checking them anymore.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
September 29 2018 15:07 GMT
#19460
On September 29 2018 03:28 raNazUra wrote:
Show nested quote +
i am working on the hamiltonian cycle problem right now actually, not TSP. I do believe TSP will end up being a much more difficult problem than hamiltonian cycle.


This is a bit of a mistake. The whole point of NP-complete problems is that if you can solve one, you've solved them all. The transformation between them is already discovered. It may be circuitous, but it exists and is known.


Well, what currently exists is completely absurd, and I haven't even heard of it being done in practice. The *only* conversion I have heard of is TSP --> sat --> 3sat ---> vertex cover ---> HC, and you'll end up with a hilariously large HC problem. So, when I say "more difficult", I am probably misusing language, but I didn't necessarily mean polynomial vs exponential time (or whatever other technical metrics there are).
Prev 1 971 972 973 974 975 1032 Next
Please log in or register to reply.
Live Events Refresh
Next event in 3h 31m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RuFF_SC2 217
SortOf 91
ProTech59
StarCraft: Brood War
Hyuk 240
ToSsGirL 168
Bale 32
Noble 24
ZergMaN 21
sOs 12
Force[name] 7
Icarus 7
League of Legends
JimRising 791
Super Smash Bros
Mew2King84
Heroes of the Storm
Trikslyr49
Other Games
summit1g12356
WinterStarcraft565
C9.Mang0319
ViBE66
Happy58
Organizations
Other Games
gamesdonequick768
[ Show 10 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2184
League of Legends
• Rush1378
Upcoming Events
The PondCast
3h 31m
University League
3h 31m
LiuLi Cup
4h 31m
Rogue vs TBD
Maru vs TBD
OSC
9h 31m
Replay Cast
16h 31m
GSL
1d 5h
Maru vs Dark
Patches Events
1d 7h
OSC
1d 9h
Replay Cast
1d 16h
KCM Race Survival
2 days
[ Show More ]
Ultimate Battle
2 days
ZerO vs Bisu
RSL Revival
3 days
BSL
3 days
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
4 days
IPSL
4 days
Ret vs ggnore13
nOmaD vs Aether
BSL
4 days
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
4 days
WardiTV Weekly
5 days
Kung Fu Cup
6 days
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
6 days
Liquipedia Results

Completed

Proleague 2026-11-16
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

Sector 591
YSL S4
SC4ALL II: Brood War
NBSL 2026 Xiamen LAN
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.