Proposed resolution:

This wording is relative to N4594.

1. Change the <algorithm> header synopsis, [algorithms.general], as indicated, to remove "constexpr" from the six {min,max,minmax}_element overloads with an ExecutionPolicy argument:

   namespace std {
   
   […]
   // 25.5.7, minimum and maximum:
   […]
   template<class ExecutionPolicy, class ForwardIterator>
     constexpr ForwardIterator min_element(ExecutionPolicy&& exec, // see 25.2.5
                                           ForwardIterator first, ForwardIterator last);
   template<class ExecutionPolicy, class ForwardIterator, class Compare>
     constexpr ForwardIterator min_element(ExecutionPolicy&& exec, // see 25.2.5
                                           ForwardIterator first, ForwardIterator last,
                                           Compare comp);
   […]
   template<class ExecutionPolicy, class ForwardIterator>
     constexpr ForwardIterator max_element(ExecutionPolicy&& exec, // see 25.2.5
                                           ForwardIterator first, ForwardIterator last);
   template<class ExecutionPolicy, class ForwardIterator, class Compare>
     constexpr ForwardIterator max_element(ExecutionPolicy&& exec, // see 25.2.5
                                           ForwardIterator first, ForwardIterator last,
                                           Compare comp);
   […]
   template<class ExecutionPolicy, class ForwardIterator>
     constexpr pair<ForwardIterator, ForwardIterator>
       minmax_element(ExecutionPolicy&& exec, // see 25.2.5
                      ForwardIterator first, ForwardIterator last);
   template<class ExecutionPolicy, class ForwardIterator, class Compare>
     constexpr pair<ForwardIterator, ForwardIterator>
       minmax_element(ExecutionPolicy&& exec, // see 25.2.5
                      ForwardIterator first, ForwardIterator last, Compare comp);
   […]
   }
   

[ 2016-06 Oulu ]

Moved to P0/Ready during issues prioritization.

Friday: status to Immediate

In LEWG we noticed some parallel algorithms are constexpr. Jared said:

I think this is an oversight, and it also applies to std::max_element/std::minmax_element. To my knowledge, neither SG1 nor LWG ever explicitly considered whether a parallel algorithm should be constexpr. I think the assumption was that parallel algorithms would be regular old function templates without additional specifiers such as constexpr.