Anybody good at maths?

[Ayahuasca]

I am a bit stuck on a maths question.

I am willing to give £5 to anyone who can give me the answer.

The question is this, and it is quite simple:

can every mathematical problem (whose answer can be easily checked by a computer) be solved in the first place by a computer within a reasonable time?

I am just looking for proof that it can.

Thanks.

Again, £5 to the first one to give me the proof.

[TooMany2cvs]

Ayahuasca said:

The question is this, and it is quite simple:

can every mathematical problem (whose answer can be easily checked by a computer) be solved in the first place by a computer within a reasonable time?

I am just looking for proof that it can.

It can't.

https://en.wikipedia.org/wiki/G%C3%B6del%27s_incom...

Ayahuasca said:

Again, £5 to the first one to give me the proof.

He died in 1978.

At least, that's if you're asking what I think you're asking.
If you're asking the other possible, then - define "reasonable time"? The assymetry of checking and back-calculating is what underpins public-private key encryption, which underpins internet security. </oversimplification>

[nyt]

I think that you're asking about the classic "P versus NP" problem in computer science: https://en.wikipedia.org/wiki/P_versus_NP_problem
The answer at the moment is that we don't know the answer. Most research suggests that not all problems that can be verified easily can be solved in non-geometric time.

[Ayahuasca]

TooMany2cvs said:

define "reasonable time"?

Let's go with, er, polynomial time, where the time taken increases geometrically with the size of the problem, and not 'exponential' time where it increases, hum, exponentially.

£5 to you if you can do this for me!

[Vaud]

Which part of your uni work are we helping you with? CompSci prep?

[Ayahuasca]

Vaud said:

Which part of your uni work are we helping you with? CompSci prep?

Does that matter?

Come on, how hard can the question be?

£5 in it for you!

[paua]

My maths doesn't stretch that far, however I did find someone offering US$1m to solve the same problem,, so you stand to make a bit of a profit there.

[Vaud]

Ayahuasca said:

Does that matter?

Come on, how hard can the question be?

£5 in it for you!

https://en.wikipedia.org/wiki/P_versus_NP_problem

And you get a $1,000,000?

[Ayahuasca]

paua said:

My maths doesn't stretch that far, however I did find someone offering US$1m to solve the same problem,, so you stand to make a bit of a profit there.

They must really be stuck with their homework!

[glenrobbo]

The answer to your question is:
exp((-(((x-4)^2+(y-4)^2)^2))/1000)+exp((-(((x+4)^2+(y+4)^2)^2))/1000)+0.15*exp(-(((x+4)^2+(y+4)^2)^2))+0.15*exp(-(((x-4)^2+(y-4)^2)^2))
AICMFP.

Either that or 42.

[Cold]

Start off with a simple calculation and extrapolate from there. Divide 22 by 7 to an accurate amount.

[4x4Tyke]

Ayahuasca said:

I am a bit stuck on a maths question.

I am willing to give £5 to anyone who can give me the answer.

The question is this, and it is quite simple:

can every mathematical problem (whose answer can be easily checked by a computer) be solved in the first place by a computer within a reasonable time?

I am just looking for proof that it can.

Thanks.

Again, £5 to the first one to give me the proof.

N != NP

I claim my five pounds.

[Zad]

You are going to be looking for a long long time. Possibly until the heat death of the universe. Which, with a certain amount of irony, will mean an exhaustive search for an NP->P mapping hasn't completed and so cannot say conclusively that one doesn't exist, whilst at the same time itself being a problem which has not itself been solved in P time.

Absence of evidence is not evidence of absence.

These may help you.

https://www.youtube.com/watch?v=dJUEkjxylBw
https://www.youtube.com/watch?v=i7sm9dzFtEI

[anonymous-user]

I started reading those Wiki links in this thread last night.

Just woke up

Damn maths is boring

[Ayahuasca]

I came across a Radio 4 In Our Time (ironic title in this case) program about it. Apparently if a positive answer is ever found the internet will break.


Also interesting is the 'travelling salesman' problem. How do you work out the cheapest way of visiting multiple locations? Rules are that you can only visit each place once and must end up where you started. Apparently that has no solution either. I wonder how postmen do it?

[Vaud]

Ayahuasca said:

Also interesting is the 'travelling salesman' problem. How do you work out the cheapest way of visiting multiple locations? Rules are that you can only visit each place once and must end up where you started. Apparently that has no solution either. I wonder how postmen do it?

They are delivering to a fixed (ish) map with low complexity. They may not be doing it in the most efficient way.

The travelling salesman problem is more complex.

[Jinx]

Vaud said:

Ayahuasca said:

Also interesting is the 'travelling salesman' problem. How do you work out the cheapest way of visiting multiple locations? Rules are that you can only visit each place once and must end up where you started. Apparently that has no solution either. I wonder how postmen do it?

They are delivering to a fixed (ish) map with low complexity. They may not be doing it in the most efficient way.

The travelling salesman problem is more complex.

Sub-contracting or franchising QED

[dcb]

anonymous said:

[redacted]

Not quite. Some partial solutions clearly aren't part of an optimal solution,
so can be rejected early.

For example, in the UK context of let's say the biggest 50 towns, *any* partial
solution that has Inverness direct to Penzance in it isn't going to be optimal,
so can be rejected early.

In practice, I find that using Prim's algorithm to get an initial solution,
then tuning it in by removing all level 2 overlaps gets a good solution in
practice.

For smaller problems, remove all level 3 overlaps as well.